好像我的切入点比较奇怪？根本想不到最大众的 \(\min-\max\) 容斥做法，那么讲讲 PGF + 直接容斥做法吧！
题意：不断按照一个给定的分布的生成一个随机数 \(x\)，然后让对应的计数器 \(C_x\) 加一，问期望生成多少个随机数时第一次满足所有的 \(C_i\geq B_i\)。
首先我们设概率生成函数 \(F\) 表示进行 \(i\) 轮操作后所有计数器 \(C_i\) 都满足 \(C_i\geq B_i\) 的概率。注意不是第一次满足的概率。
这个概率生成函数似乎比较难有一个封闭形式，因为满足 \(C_i\geq B_i\) 的 \(C_i\) 是无限的无法枚举。
那么考虑一个套路：直接上普通容斥！接下来我们用一个由 \(\geq,<,-\) 字符串来表示 \(C_i\) 与 \(B_i\) 之间的关系是大于等于/小于/没有限制。
我们发现，题目中要求的 \(F\) 就是 \(F_{\geq \geq \geq \dots \geq}\)，而我们后面会看到好求的 \(F\) 都是只有 \(<\) 和 \(-\) 的形式。考虑逐个将 \(F\) 容斥成后者的形式，我们就可以发现 容斥系数正好就是 \(<\) 号的个数。
于是我们转而去考虑这样一个问题：强制计数器的若干个位置小于一个给定值，那么它的 PGF 是什么。\(<B_i\) 的位置是有限的，设这些位置组成的集合是 \(S\)，所以我们暴力枚举这些位置的 \(C_i\)，然后用一个多重组合数计算它们拼成一个长度为 \(\sum_{i\in S} C_i\) 的序列的方案数，也就是 \(\frac{(\sum_{i\in S} C_i)!}{\prod_{i\in S} C_i!}\)。
记 \(a=\sum_{i\in S} C_i\)，我们再考虑怎么算 PGF。设生成一个 \(\in S\) 的随机数的概率是 \(p\)，我们枚举 \(\notin S\) 的数的出现次数 \(t\)，然后把这些数插入到刚才钦定的序列，有:
那么 \(F=\sum_S (-1)^{|S|}F_S\)。现在，如果只是单纯算下不只是第一次出现的期望，那么直接算 \(F'(1)\) 就可以了。然后考虑如何处理“第一次”这个条件：我们直接差分，乘上 \((1-x)\) 就可以了！因为 \([x^i]F\) 也可以看成是第一次满足的时间 \(\leq i\) 的概率。
于是我们要求的就是 \(\frac{x^a(1-x)}{[1-(1-p)x]^{a+1}}\) 的导数在 \(x=1\) 处的取值，用商的求导法则计算得到是 \(-p^{-a-1}\)(Wolfram)。
于是我们把 \(A_i,C_i\) 当作体积直接背包出 \(p,a\)，中途乘上一些相关贡献，由于 \(\sum B_i\) 不大，复杂度 \(O(\sum A_i (\sum B_i)^2)\)。
#include <cstdio>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=403,P=998244353;
typedef long long ll;
int n,sum,num,iv;
int f[N][N],a[N],b[N];
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
int fac[N],fiv[N];
void init(int lim){
fac[0]=1;
for(int i=1;i<=lim;++i) fac[i]=(ll)fac[i-1]*i%P;
fiv[lim]=qp(fac[lim]);
for(int i=lim;~i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
}
void dec(int &x,int v){if((x-=v)<0) x+=P;}
int main(){
n=read();f[0][0]=P-1;init(400);
for(int x=1;x<=n;++x) a[x]=read(),b[x]=read(),iv+=a[x];
iv=qp(iv);
for(int x=1;x<=n;++x){
int p=(ll)a[x]*iv%P;
for(int i=sum;~i;--i)
for(int j=num;~j;--j){
int pw=1;
if(!f[i][j]) continue;
for(int t=0;t<b[x];++t){
dec(f[i+a[x]][j+t],(ll)fiv[t]*pw%P*f[i][j]%P);
pw=(ll)pw*p%P;
}
}
num+=b[x]-1;
sum+=a[x];
}
int res=0;
for(int i=0;i<=sum;++i){
int p=(ll)i*iv%P;
for(int j=0;j<=num;++j)
res=(res+(ll)f[i][j]*qp(p,P-2-j)%P*fac[j]%P)%P;
}
printf("%d\n",res);
return 0;
}
跟其它的做法殊途同归了。