【AT5202】[AGC038E] Gachapon（Min-Max容斥）
- 有一个随机数生成器，每轮随机生成一个([1,n])的整数，有(frac{a_i}{sum a_i})的概率生成(i)。
- 求所有(i)的出现次数都达到各自(b_i)的期望轮数。
- (n,sum A,sum Ble400)
(Min-Max)容斥
刚好想着要做一道(Min-Max)容斥题，没想到就撞上了这题。
像这种对出现次数有要求的问题一看就超级(Min-Max)容斥。
根据它的公式：
[E(max(S))=sum_{Tsubseteq S}(-1)^{|T|+1}E(min(T))
]
要求所有(i)都达成限制就是(E(max(S)))，而集合(T)内只要有一个满足限制就是(E(min(T)))，显然要好算许多。
式子推导
考虑如何计算(T)，那么就枚举产生(T)集合中的数的轮数(k)。
记(A=sum_{i=1}^n a_i,s(T)=sum_{iin T}a_i)，由于一轮产生的数在(T)中的概率为(frac {s(T)}A)，因此实际上需要的轮数应该是(k imesfrac{A}{s(T)})。
而要求(k)轮有一个数达成限制的概率，实际上就是算每一轮都没有数达成限制的概率，那相当于把(k)分配到(c_{1sim |T|})使得所有(c_i<b_i)。
于是列出式子：（(B=sum_{iin T}(b_i-1))）
[sum_{k=0}^Bfrac A{s(T)}sum_{sum_{iin T}c_i=k}frac{k!}{prod_{iin T}c_i!}prod_{iin T}(frac{a_i}{A})^{c_i}\
sum_{k=0}^Bfrac {Ak!}{s(T)^{k+1}}sum_{sum_{iin T}c_i=k}prod_{iin T}frac{a_i^{c_i}}{c_i!}
]
最后算上容斥的(DP)系数：
[(-1)^{|T|+1}sum_{k=0}^Bfrac {Ak!}{s(T)^{k+1}}sum_{sum_{iin T}c_i=k}prod_{iin T}frac{a_i^{c_i}}{c_i!}
]
然后就是考虑这个式子的求值即可。
(DP)求解
发现这个式子中，(k!)和(s(T)^{k+1})算是比较麻烦的项，因此我们考虑把(s(T))和(k)两个值设入(DP)的状态中。
那么只要设(f_{i,j,k})表示处理了前(i)个数，选出的(sum a_i=T)，选择的(sum c_i=k)时((-1)^{|T|+1}prodfrac{a_i^{c_i}}{c_i!})的总和。
转移就分两种状态，不选或是选(l)个，后者需要给状态乘上容斥系数(-1)。
(DP)的转移和最后的求解应该都是非常简单的，细节之类的也没啥吧。
就是要注意(DP)的初值为(f_{0,0,0}=(-1)^{0+1}=-1)。
复杂度分析一下，是(O(nABl))的，但实际上能选择的(sum l=B)，因此复杂度是(O(AB^2))。
(O(AB^2))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 400
#define X 998244353
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
#define Dec(x,y) ((x-=(y))<0&&(x+=X))
using namespace std;
int n,a[N+5],b[N+5],f[N+5][N+5][N+5],Fac[N+5],IFac[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,j,k,l,t,A=0,B=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",a+i,b+i);
for(Fac[0]=i=1;i<=N;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[i=N]=QP(Fac[N],X-2);i;--i) IFac[i-1]=1LL*IFac[i]*i%X;//预处理阶乘逆元
for(f[0][0][0]=X-1,i=1;i<=n;A+=a[i],B+=b[i++]-1) for(j=0;j<=A;++j) for(k=0;k<=B;++k)//容斥的DP求解
{
Inc(f[i][j][k],f[i-1][j][k]);//不选
for(t=1,l=0;l^b[i];t=1LL*t*a[i]%X,++l) Dec(f[i][j+a[i]][k+l],1LL*f[i-1][j][k]*t%X*IFac[l]%X);//选l个
}
for(t=0,j=1;j<=A;++j) for(k=0;k<=B;++k)//最后答案的求解
Inc(t,1LL*A*Fac[k]%X*QP(QP(j,X-2),k+1)%X*f[n][j][k]%X);return printf("%d
",t),0;//利用j和k计算
}