[数学记录]AT5202 [AGC038E] Gachapon
command_block
2021-07-14 08:09:53
**题意** ： 给出权值数组 $A_{1\sim n}$ ，记 $S=\sum A_{1\sim n}$。
有一个随机数生成器，每次会以 $A_i/S$ 的概率生成数 $i$。
这个随机数生成器不断生成随机数，当所有 $i$ 至少出现 $B_i$ 次时停止，问期望生成的次数。
答案对 $998244353$ 取模。
$n,\sum A,\sum B\leq 400$ ，时限$\texttt{3s}$。
------------
组合苦弱，代数飞升。我们已经知道这类问题的代数结构，直接大力推式即可。
改记 $A_i\leftarrow A_i/S$。
记生成 $n$ 次时满足“所有 $i$ 至少出现 $B_i$ 次”的概率为 $P[n]$ ，使用 (P)EGF 刻画排列，有 ：
$$F(x)=\prod_{i=1}^n\sum\limits_{j=B_i}^{+\infty}\dfrac{(A_ix)^j}{j!}$$
$$P[n]=[x^n/n!]F(x)$$
注意到这同时也是耗时 $T\leq i$ 的概率。于是有 ：
$${\rm Ans}=E(T)=\sum_{i=0}^{+\infty}P(T>i)=\sum_{i=0}^{+\infty}1-P[i]$$
先将 $F$ 变形为更简单的形式。
$$
\begin{aligned}
F(x)&=\prod_{i=1}^n\sum\limits_{j=B_i}^{+\infty}\dfrac{(A_ix)^j}{j!}\\
&=\prod_{i=1}^n\Big(e^{A_ix}-\sum\limits_{j=0}^{B_i-1}\dfrac{(A_ix)^j}{j!}\Big)
\end{aligned}
$$
我们令 $y=e^x$ ，将其看做二元生成函数。
可以发现 $F$ 能表示为 $\sum_{c}y^cG_c(x)$ 的形式。其中 $G_c(x)$ 是多项式。
具体地，$c$ 的可能取值有 $S$ 个，$G$ 的次数是 $\sum B$ 的。
暴力计算，逐个相乘，复杂度为 $O\big(S(\sum B)^2\big)$ ，此处是复杂度瓶颈。
$$
\begin{aligned}
{\rm Ans}&=\sum_{n=0}^{+\infty}1-P[i]\\
&=\sum_{n=0}^{+\infty}1-[x^n/n!]\sum_{c}e^{cx}G_c(x)\\
\end{aligned}
$$
注意到 $G_{1}(x)=1$ （因为在每个因式中都选了 $e^{A_ix}$ 而 $\sum A=1$），用这一项 $[x^n/n!]e^x$ 抵消掉前面的 $1$。
$$
\begin{aligned}
&=\sum_{n=0}^{+\infty}[x^n/n!]\sum_{c,c\neq 1}e^{cx}G_c(x)\\
&=\sum_{n=0}^{+\infty}n!\sum_{c,c\neq 1}\sum_{j=0}^{+\infty}G_c[j][x^{n-j}]e^{cx}\\
&=\sum_{n=0}^{+\infty}n!\sum_{c,c\neq 1}\sum_{j=0}^{+\infty}G_c[j]\dfrac{c^{n-j}}{(n-j)!}\\
&=\sum_{c,c\neq 1}\sum_{j=0}^{+\infty}G_c[j]\sum_{n=0}^{+\infty}n^{\underline j}c^{n-j}\\
&=\sum_{c,c\neq 1}\sum_{j=0}^{+\infty}G_c[j]c^{-j}j!\sum_{n=0}^{+\infty}\binom{n}{j}c^n\\
\end{aligned}
$$
记 $S_j(c)=\sum_{n=0}^{+\infty}\binom{n}{j}c^n$ ，则有 ：
$$
\begin{aligned}
S_j(c)&=\sum_{n=0}^{+\infty}\binom{n}{j}c^n\\
&=\sum_{n=0}^{+\infty}\binom{n-1}{j}c^n+\sum_{n=1}^{+\infty}\binom{n-1}{j-1}c^n\\
&=cS_j(c)+cS_{j-1}(c)\\
&\Rightarrow S_j(c)=\dfrac{c}{1-c}S_{j-1}(c)
\end{aligned}
$$
可以递推求出所需的 $S_j(c)$ 。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define Poly vector<int>
#define MaxN 405
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
int fac[MaxN],ifac[MaxN];
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=1ll*ifac[i]*i%mod;
}
Poly operator * (const Poly &A,const Poly &B){
Poly C;C.resize(A.size()+B.size()-1);
for (int i=0;i<A.size();i++)
for (int j=0;j<B.size();j++)
C[i+j]=(C[i+j]+1ll*A[i]*B[j])%mod;
return C;
}
void add(Poly &A,Poly &B){
if (A.size()<B.size())A.resize(B.size());
for (int i=0;i<B.size();i++)A[i]=(A[i]+B[i])%mod;
}
Poly G[MaxN];
int n,S,a[MaxN],b[MaxN],s[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
int S=0,S2=0;
for (int i=1;i<=n;i++){S+=a[i];S2+=b[i];}
int invS=powM(S);Init(S2);
G[0].push_back(1);
for (int i=1;i<=n;i++){
Poly R;R.resize(b[i]);
int buf=1,sav=1ll*a[i]*invS%mod;
for (int j=0;j<b[i];j++){
R[j]=mod-1ll*buf*ifac[j]%mod;
buf=1ll*buf*sav%mod;
}
for (int k=S-a[i];k>=0;k--){
add(G[k+a[i]],G[k]);
G[k]=G[k]*R;
}
}
int ans=0;
for (int i=0;i<G[0].size();i++)
ans=(ans+1ll*G[0][i]*fac[i])%mod;
for (int k=1;k<S;k++){
int c=1ll*k*invS%mod,invc=powM(c),buf=1;
s[0]=powM(mod+1-c);
for (int i=1;i<G[k].size();i++)
s[i]=1ll*s[i-1]*s[0]%mod*c%mod;
for (int i=0;i<G[k].size();i++){
ans=(ans+1ll*G[k][i]*buf%mod*fac[i]%mod*s[i])%mod;
buf=1ll*buf*invc%mod;
}
}printf("%d",(mod-ans)%mod);
return 0;
}
```