CF248E.Piglets Birthday-概率、DP

link：https://codeforces.com/contest/248/problem/E

题意：有 \(n\) 个货架，第 \(i\) 个货架初始有 \(a_i\) 罐蜂蜜，有 \(q\) 次操作，每次操作从 \(u\) 货架上等概率地选出 \(k\) 罐蜂蜜，尝一口，再放到 \(v\) 货架上，然后询问期望有多少个货架，上面每罐蜂蜜都被尝过。

\(n,q\leq 10^5,a_i\leq 100,k\leq 5\).

---

看数据范围， \(k\leq 5\)…好像只看这个也不能想到什么，但首先要意识到这个应该是有用的。

吃蜂蜜当成打标记：\(i\) 货架有 \(a_i\) 个小球，初始标记都是 \(0\) ，每次等概率选 \(k\) 个，打上 \(1\) 的标记，放到 \(v\) 上。很明显，被放到 \(v\) 上的蜂蜜一定是打过标记的。
刚开始的时候我想的是对被打过标记的蜂蜜进行DP，\(f(i,j)\) 表示 \(i\) 货架上有 \(j\) 罐蜂蜜被打过标记（被尝过）的概率，一次转移是 \(O(k\times a_i)\) 的，但这样复杂度是不对的，比如把很多罐蜂蜜都放到一个货架上， \(a_i\) 会长到 1e5 的范围，然后再把这些蜂蜜转移到其他地方，复杂度就爆炸了。

所以DP的时候也应当注意到这样一个关系，打过标记的蜂蜜越来越多，没打过标记的越来越少，同时，对每个货架来说，没被打过标记的也是越来越少的。

因此应该让 \(f(i,j)\) 表示，\(i\) 货架有 \(j\) 罐蜂蜜没打过标记的概率，答案是 \(\sum f(i,0)\)，转移则只要考虑 \(u\) ：

\[\frac{\binom{j}{i}\times \binom{a-j}{k-i}}{\binom{a}{k}}\cdot f(v,j)\to f_{new}(v,j-i) \]

预处理组合数（第二维 \(\leq k\)，\(O(\max a_i\times k)\) 暴力处理就好），\(O(\max a_i \times k)\) 地转移

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+5;
const int C=105;
const int MX=5e5+50;
int n,q,a[N],mx[N];
double f[N][C],g[C],binom[MX][6];
int main(){fastio;cin>>n;rep(i,1,n){cin>>a[i];mx[i]=a[i];f[i][a[i]]=1;}rep(i,0,MX-5){binom[i][0]=1;rep(j,1,min(i,5))binom[i][j]=binom[i-1][j]+binom[i-1][j-1];}double ans=0;rep(i,1,n)ans+=f[i][0];cin>>q;while(q--){int u,v,k;cin>>u>>v>>k;ans-=f[u][0];rep(i,0,mx[u]){g[i]=f[u][i];f[u][i]=0;}rep(j,0,mx[u])rep(x,0,k)f[u][j-x]+=binom[j][x]*binom[a[u]-j][k-x]/binom[a[u]][k]*g[j];a[u]-=k;a[v]+=k;ans+=f[u][0];cout<<fixed<<setprecision(12)<<ans<<endl;}return 0;
}

顺带一提-Vandermonde卷积

上面DP转移里出现了转移系数：枚举状态 \(f(v,j)\) 的所有转移，所有转移的概率之和必然是 \(1\)，那么有：

\[\sum_{i}\binom{j}{i}\times \binom{a-j}{k-i}=\binom{a}{k} \]

这个就是Vandermonde卷积公式啦，用题目中的例子就可以很好地解释其组合含义：有 \(a\) 个小球，有 \(j\) 个是好的，\(a-j\) 个是坏的，从中无序地选出 \(k\) 个，共有 \(\binom{a}{k}\) 种选择方式，而从另一角度考虑：枚举选了 \(i\) 个好球和 \(k-i\) 个坏球，算出来的方案自然是一样的。