2020 CCPC Weihai E. So Many Possibilities... 题解 feat. minstdfx

· · 个人记录

题意：有 N(1\le N\le15) 个随从，每个随从有 a_i(1\le a_i\le 100) 的生命。一旦某个随从的生命变成 0，他就会被击杀。现在你需要进行 M(1\le M\le 100,M \le\sum a_i) 次伤害操作，每次操作等概率选取一个存活的随从并造成 1 点伤害。求最终击杀的随从数量的期望。

我一开始想把所有可能的操作序列拿出来然后怎么容斥着计算一下，然后看样例就发现它是错的，因为不同的操作序列出现的概率不同。

接下来我想要设计一个 dp，dp_{i,S} 表示 i 的时刻击杀的集合恰好是 S 的概率。这个时候可以观察到，对于每一个仍然存活的随从，它在前面 i-\sum_{j\in S}a_j 次操作中受到伤害的期望次数全部是相等的。所以我考虑枚举下一个被击杀的随从以及击杀的时间，那么这个过程中不能击杀其他的随从。因此需要容斥计算，时间复杂度 O(3^nnm) 或者 O(4^nnm)，不清楚细节也不清楚这样转移是不是对的，总之时间肯定炸了。

然后我去看了题解，发现了一个重要的观察：我并不需要保证过程中不击杀其他的随从。我设一个操作序列 \Gamma_{i,S} 表示前 i 步击杀了 S 中的随从时的操作序列，满足 |\Gamma_{i,S}=i|,\forall X\in S,\sum_{j\in \Gamma}[j=X]=a_X 且 \forall X\in \Gamma_{i,S},X\in S \bigvee X=0。这里定义 X=0 表示这一步操作没有攻击 S 内的随从。

这样我就不需要推 dp 的时候考虑会不会误杀其他的随从了，因为可以在计算答案的时候，对于某一个状态对于所有 0 的位置计算这些位置无法杀死任意一个其他随从的概率（把这个东西记为 g_{m,S}）即可。

记 S'_{i,S} 是 \Gamma_{i,S} 构成的集合，那么可以设 dp_{i,S}=\sum_{P \in S'_{i,S}}p(P)，其中 p(\Gamma) 表示 \Gamma 序列出现的概率。

接下来就应该推转移了。但是我现在只知道如果下一步会击杀新的随从，转移式里会有一个组合数（从当前序列里所有的 0 里选出若干次给当前随从），另外我发现我又完全不会了！因此我需要请求一个特殊工具。 :::info[来自 minstdfx 的补充(UPD at 21:42)] Note: 我们定义 dp_{S,m} 表示前 m 次操作，恰好击杀的集合是 S 的，不考虑与 S 无关的操作的概率乘数。这个东西其实就是实际概率去除以放置无关操作的方案数，因为这两者是相互独立的。

显然我们有 dp_{\varnothing,0}=1,dp_{\varnothing,m}=dp_{\varnothing,m-1}/n。

我们分两种情况讨论转移：

  1. 最后一次操作干掉了一个 u\in S。
    那么最后一次打到 u 的概率是 \frac 1 {n-|S|+1}。 在前 m-1 次操作中，有 \sum_{i\in S,i\neq u} a_i 次打中其他随从，有 a_u-1 次打中 u，其余都是打中别的，也就是 0。挑出 m-1-\sum_{i\in S,i\neq u} a_i 个位置中的 a_i-1 个给 u，那么就是
  2. 最后一次操作是未命中，也就是0
    这个简单啊，就是 dp_{S,m-1}/(n-|S|)。

那么如何计算答案呢？ 我们假设最终死掉的集合为 S，那么一共会有 m-\sum_{i\in S} a_i 次攻击落在其他的随从上，并且不能死任何其他的随从。因此答案为

\sum_{S\subseteq \{1,2,\cdots n\},m\ge \sum_{i\in S} a_i} |S|\times dp_{S,m}\times g_{S^c,m-\sum_{i\in S} a_i}

其中 g_{S,c} 表示 c 次攻击落在 S 的集合上打不死任何随从的方案数。

如何计算 g 呢？我们钦点最后一个元素 p，那么

g_{S,c}=\sum_{i=0}^{\min\{a_p-1,c\}} \binom c i\cdot g_{S\backslash p,c-i}

:::

我看到这个的时候，我产生了一个问题：为什么要在转移 dp 的时候除以选择数呢？同时 fx 给到的 g 数组的定义也和我前面定义的不同，是方案数而非概率。我猜想这是因为“不同的操作序列出现的概率不同”这个问题仍然没被解决（虽然我还没完全明白为什么这样转移就可以算出正确的概率）。 :::error[补充2] 其实一开始我看到你有疑问我很好奇。主要是当时我写这个的时候你可能自己定义了 g，但是完全没有把它写到文章里，所以我不知道你自己还定义了 g，我就自己定义了一个需要用到的。但是后来我发现我在编辑文章的过程中可能是因为编辑器的神秘快捷键或是什么其他原因，居然删掉了最重要的第一行，也就是说明我的 dp 代表什么意思的一行，可能造成了理解上的混乱，现在我将它补上。

接下来我相信不需要解释为什么要在转移 dp 的时候除以选择数了。

在做转移时，考察 dp 的定义，我们只需要把这种等概率选人的概率因子乘进去；而非致死的攻击到底分给了谁以及顺序怎么排的组合个数交给 g 和组合数去统计。
所以在 dp 里每插入一步操作，就必须除以当时可被选中的人数。 ::: 总时间复杂度 O(2^n(n+m)m)。

这个题有一个坑，就是有可能 \sum a=m，需要防止除 0。

int a[20],sum[40000];
long double F[110][80000],G[110][80000],C[110][110];
void solve(){
  int n,m;read(n),read(m);
  rep(i,0,n-1)read(a[i]);
  rep(i,0,(1<<n)-1)rep(j,0,n-1)if((i>>j)&1)sum[i]+=a[j];
  rep(i,0,m)C[i][0]=C[i][i]=1;
  rep(i,1,m)rep(j,1,i-1)C[i][j]=C[i-1][j]+C[i-1][j-1];
  F[0][0]=1e300;
  rep(i,1,m){
    rep(j,0,(1<<n)-1){
      int S=__builtin_popcount(j);
      if(n!=S)F[i][j]+=F[i-1][j]/(n-S);
      rep(k,0,n-1)if((j>>k)&1){
        int R=i-sum[j];if(R<0)continue;
        F[i][j]+=F[i-1][j^(1<<k)]*C[i-sum[j^(1<<k)]-1][a[k]-1]/(n-S+1);
      }
    }
  }
  G[0][0]=1;
  rep(i,0,m)rep(j,1,(1<<n)-1){
    int X=__builtin_ctz(j);
    rep(k,0,a[X]-1)if(i>=k)G[i][j]+=C[i][k]*G[i-k][j^(1<<X)];
  }
  long double ans=0;
  rep(i,0,(1<<n)-1){
    if(sum[i]<=m)ans+=__builtin_popcount(i)*F[m][i]*G[m-sum[i]][(1<<n)-1-i];
  }
  printf("%.12Lf\n",ans/F[0][0]);
}