CCPC2020 Weihai E
问题描述
在游戏“炉石传说”中,存在一张卡牌”考古专家雷诺”,其在特定条件下会对敌方所有随从随机地进行总量为10点的伤害。而其随机方式是对于每一点伤害依次进行判定,等概率地从所有敌方的存活随从中选择一个进行伤害。我们关注于对于某特定随从序列其杀死随从数量的期望,并将其伤害从常数 $10$ 推广到某一给定数值 $m$,得到如下问题:
- 对某一正项序列 $a_1,a_2,\cdots,a_n$ ,依次进行 $m$ 次操作,每次在所有非零项 $a_{p_1},a_{p_2}, \cdots,a_{p_m}$ 中等概率地选取一个数 $a_{p_i}$ 并令 $a_{p_i}=a_{p_i}-1$ 。记 $m$ 次后的非零项个数为 $x$ ,求 $x$ 的期望 $E(x)$.
问题解法
定义 $S_l= \{s_1,s_2,\cdots,s_l \}$ 表示一个长度为 $l$ 的操作序列,其中,$s_i \in[1,n]$ 表示第 $i$ 次操作选取了 $a_{s_i}$ .
令 $ \sigma_i^{S_l}$ 表示经 $S_l$ 的前 $i$ 次操作后,序列 $ \{a_i\}$ 剩余的非零项的个数。特别地,令 $ \sigma^{S_l}= \sigma_l^{S_l}$ 表示经过全部 $S_l$ 的操作后,其非零项的个数。
那么,每个合法操作序列出现的概率
定义 $\Gamma$ 为所有长度为 $m$ 的合法操作序列的集合,则
接下来,我们将问题的求解分为两个步骤。
Part I
定义集合 $\Gamma_{l,Set}$ $0 \le l \le m,Set \subseteq [n]$ 是序列 $S= \{s_1,s_2, \cdots,s_n \}$ 的集合,要求序列满足:
- $ \forall 1 \le i \le n,s_i=0 || s_i \in Set$
- $ \forall j \in S,cnt_j(Set)=a_j$
其中,$s_i=0$ 代表第 $i$ 次操作的对象 $\notin Set$ , $cnt_i(S)$ 表示序列 $S$ 中 $i$ 的出现次数
设 $f_{l,Set} (0 \le l \le m,Set \subseteq [n])$ 为
则有,
其中,
递推式中的第一项表示 $s_l=0$ 的概率,后面则是枚举 $s_l=i$ 且 $cnt_i(S)=a_i$ 的概率,将这两类情况求和,即为满足条件的总概率.
可以通过预处理所有的 $sum(A)$ 以及 $|A|$ 使这个递推式可以在 $O(nm2^n)$ 的时间内完成.
Part II
可以发现,$ \forall S \in \Gamma_{m,Set},cnt_0(S)$ 恒定,所以只需考虑 $s_i=0$ 的位置,给每个位置赋上不属于 $Set$ 的值,并且满足$ \forall i \notin Set,cnt_i(S)<a_i$ 即可得到一个合法的序列.记这样的方案总数为 $g_{Set}$,则有:
令 $h_{l,Set}$,表示序列 $S’= \{s_1,s_2,\cdots,s_l\}$ 满足:
- $\forall 1 \le i \le l,s_i \in Set $
- $\forall i \in Set,cnt_i(S’)<a_i $
的个数,则 $h_{m-|Set|,Set}=g_{Set^{C}}$,所以只要求得 $h_{i,Set}$ 序列即可.
易得递推式
其中,$low(Set)$,表示 $Set$ 中的最小元素.
上述递推可以在 $O(m^2 2^n)$ 的时间内完成.
综上,问题得解.总时间复杂度为 $O(m(n+m)2^n)$.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<iostream> #include<cstdio> using namespace std; const int MAXN=5e4+100; double fac[MAXN],fav[MAXN],dp[110][MAXN],fir[MAXN][110]; int n,m,dat[MAXN],sum[MAXN],num[MAXN],lower[MAXN]; double qpow(double base,int tim) { double ans=1; while(tim) { if(tim&1) ans*=base; base*=base;tim>>=1; } return ans; } void init() { fac[0]=fac[1]=1; fav[0]=fav[1]=1; for(int i=2;i<=MAXN-100;i++) { fac[i]=fac[i-1]*i; fav[i]=fav[i-1]/i; } } double C(int a,int b) { return fac[b]*fav[a]*fav[b-a]; } double get_dp(int x,int res) { if(fir[x][res]>(1e-8)) return fir[x][res]; int now=lower[x]; if(res==0) fir[x][res]=1; else for(int i=0;i<=dat[now]-1;i++) fir[x][res]+=get_dp(x^(1<<now-1),res-i)*C(i,res); return fir[x][res]; } int main() { cin>>n>>m;init(); for(int i=1;i<=n;i++) scanf("%d",&dat[i]); for(int i=0;i<(1<<n);i++) for(int j=1;j<=n;j++) if(i&(1<<(j-1))) { if(lower[i]==0) lower[i]=j; else lower[i]=min(lower[i],j); num[i]++; sum[i]+=dat[j]; } if(sum[(1<<n)-1]==m) { printf("%d",n); return 0; } dp[0][0]=1; for(int i=1;i<=m;i++) for(int j=0;j<(1<<n);j++) { if(sum[j]>i) continue; if(i>sum[(1<<n)-1]-(n-num[j])) continue; dp[i][j]=dp[i-1][j]/(n-num[j]); for(int k=1;k<=n;k++) if(j&(1<<(k-1))) { double p=1.0/(n-num[j^(1<<(k-1))]);int res=i-sum[j^(1<<(k-1))]; dp[i][j]+=dp[i-1][j^(1<<(k-1))]*C(dat[k]-1,res-1)*p; } }
fir[0][0]=1; for(int i=0;i<1<<n;i++) { int now=lower[i]; for(int j=0;j<=m;j++) for(int k=0;k<=min(dat[now]-1,j);k++) fir[i][j]+=fir[i^(1<<(now-1))][j-k]*C(k,j); } double ans=0;int base=(1<<n)-1; for(int i=0;i<(1<<n);i++) if(m>=sum[i]&&fir[base^i][m-sum[i]]!=0) ans+=num[i]*dp[m][i]*fir[base^i][m-sum[i]]; printf("%.10lf \n",ans); }
|