题意

有一个随机数生成器, 每个数生成的概率是 \(\dfrac{a_i}{\sum a_j}\), 求第一次使得每个数至少出现了 \(b_i\) 次的时候总生成次数的期望. \(\sum a_i,\sum b_i \le 400\)

题解

设 \(p_i=\dfrac{a_i}{\sum a_j}\) , 即生成 \(i\) 的概率

考虑 \(\min-\max\) 容斥, 令 \(g\left(S\right)\) 表示第一次 \(S\) 中有数出现 \(\ge b_i\) 次时生成次数, 则 \(Ans=\sum_{T\subseteq\left\{1,2,\cdots n\right\},T\neq \emptyset}\left(-1\right)^{\left|T\right|-1}E\left(g\left(T\right)\right)\)

由于 \(E\left(g\left(T\right)\right)=\sum_{t\ge 0}\Pr\left(g\left(T\right)> t\right)\), \(g\left(T\right)> t\) 的意义为 \(t\) 次内所有数的出现次数分别 \(< b_i\), 那么概率函数的EGF为

\[\begin{aligned} \Pr\left(g\left(T\right)> x\right)&=\left(\prod_{k\in T}\left(\sum_{0\le i < b_k}\dfrac{p_k^i}{i!}x^i\right)\right)\cdot \left(\sum_{j\ge 0}\frac{\left(1-\sum_{k\in T}p_k\right)^j}{j!}x^j\right) \\ &=\exp\left(x\right)\prod_{k\in T}\left(\exp\left(-p_kx\right)\sum_{0\le i < b_k}\dfrac{p_k^i}{i!}x^i\right) \end{aligned} \]

那么就可以计算答案了

\[\begin{aligned} Ans&=\sum_{T\subseteq\left\{1,2,\cdots n\right\},T\neq \emptyset}\left(-1\right)^{\left|T\right|-1}E\left(g\left(T\right)\right)\\ &=-\sum_{T\subseteq\left\{1,2,\cdots n\right\},T\neq \emptyset}\sum_{i\ge 0}\left[\dfrac{x^i}{i!}\right]\left(\exp\left(x\right)\prod_{k\in T}\left(-\exp\left(-p_kx\right)\sum_{0\le i < b_k}\dfrac{p_k^i}{i!}x^i\right)\right) \end{aligned} \]

而每一项形如 \(f_kx^k\exp\left(px\right)\) 对答案的贡献为

\[\begin{aligned} \sum_{i\ge 0}\left[\dfrac{x^i}{i!}\right]\left(f_kx^k\exp\left(px\right)\right)&=\sum_{i\ge k}\dfrac{f_kp^{i-k}i!}{\left(i-k\right)!}\\ &=f_kk!\sum_{i\ge k}\dfrac{i!p^{i-k}}{k!\left(i-k\right)!}\\ &=f_kk!\sum_{i\ge 0}\binom{i+k}{k}p^{i} \\ &=f_kk!\dfrac{1}{\left(1-p\right)^{k+1}} \end{aligned} \]

但是此时复杂度依旧是指数级的, 但是注意到最终 \(e\) 的指数只有 \(0,\dfrac{1}{\sum a_j},\cdots \dfrac{\sum a_j-1}{\sum a_j}\) 共 \(\sum a_i\le 400\) 种, 所以对 \(-\exp\left(-p_kx\right)\sum_{0\le i < b_k}\dfrac{p_k^i}{i!}x^i\) 背包即可

每一个多项式的系数是 \(b_i-1\) 次的, 所以总复杂度是 \(n\cdot \sum{a_i}\cdot \sum_{i}b_i\left(\sum_{j\le i}b_j\right)=\mathcal{O}\left(n\sum a\sum b\right)\)

代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
constexpr int N=410,p=998244353;
int f[N][N],a[N],b[N],n,S,tmp[N],fac[N],ifac[N],inv[N],pr[N];
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d %d",&a[i],&b[i]),S+=a[i];
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
	for(int i=1;i<=n;++i) pr[i]=1ll*a[i]*inv[S]%p;
	f[0][0]=1;int cur=0;
	for(int i=1;i<=n;++i){
		for(int j=S;j>=a[i];--j){
			for(int k=j-a[i],g=0;g<=cur;++g)
				for(int h=0,rr=1;h<b[i];++h,rr=1ll*rr*pr[i]%p)
					f[j][g+h]=(f[j][g+h]-1ll*rr*ifac[h]%p*f[k][g]%p+p)%p;
		}
		cur+=b[i]-1;
	}
	int ans=0;
	for(int i=1;i<=S;++i){
		int pp=(1-1ll*i*inv[S]%p+p)%p,val=1ll*S*inv[i]%p;
		for(int j=0,k=val;j<=cur;++j,k=1ll*k*val%p*j%p)
			ans=(ans+1ll*k*f[i][j]%p)%p;
	}
	ans=(p-ans)%p;
	printf("%d\n",ans);
	return 0;
}