AGC038E Gachapon | Arahc's Home

题面

简化题意

有 $n$ 个数，每个数有概率 $a_i$ 和权值 $b_i$ 。每次以 $\frac{a_i}{\sum a}$ 的概率随机到第 $i$ 个数并标记。求所有数字的标记个数都不小于权值的期望随机轮数。

$n,\sum a,\sum b\leq 400$ 。

题解

所有数字被随机到的次数都不小于其权值的时间，等于最晚被随机到那么多次的数被随机到的时间。

minmax 容斥变成最早呗随机成那么多次，给：

E(\max(S)) = \sum_{T\subseteq S} (-1)^{\left|T\right|+1} E(\min(T))

问题转化为：求任意集合中至少一个数被随机到其权值那么多次的期望时间。

首先考虑随机到这个集合内的数的次数，不难得到期望 $\frac{\sum a}{\sum_{i\in T} a_i}$ 次就可以随到一次集合里的数。

至少有一个数满足条件，可以先考虑没有任何数满足条件的情况。以数组 $c$ 表示集合内各个数被随机到的次数， $c$ 对答案的贡献为：

\prod_{i\in T} (\frac{a_i}{\sum_{i\in T} a_i})^{c_i} \frac{k!}{\prod_{i\in T} c_i!}

则总贡献为：

\sum_{T\subseteq S} (-1)^{\left|T\right|+1} \left[ \sum_{k=0}^{\sum_{i\in T}(b_i - 1)} \frac{\sum a}{\sum_{j\in T} a_j} k! \prod_{i\in T} \frac{a_i^{c_i}}{c_i!(\sum_{j\in T} a_j)^{c_i}} \right]

这个式子非常吓人，但是可以 DP。设 $f_{i,j,k}$ 表示考虑到前 $i$ 个数，选择的数满足 $\sum a= j,\sum c=k$ 的贡献。转移的时候如果选择一个数加入进去，要注意容斥系数乘上了 $-1$ ，如果不加入数字则不会改变。

因此得到转移：

f_{i,j,k} \gets f_{i-1,j,k} - \sum_{p=0}^{b_i - 1} f_{i-1,j-p,k-a_i} \times \frac{a_i^p}{p!}

答案为：

\sum_i \sum_j \frac{\sum a}{i}\frac{j!}{i^j}f_{n,i,j}

因为枚举 $p$ 的总量是 $\sum b$ 的，因此复杂度为 $n^3\log n$ 。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=402,mod=998244353;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

int f[max_n][max_n][max_n],ans;
int n,a[max_n],b[max_n],fac[max_n],inv[max_n],sa,sb;

signed main(){
	n=read();
	for(register int i=1;i<=n;++i)
	    a[i]=read(),b[i]=read(),sa+=a[i],sb+=b[i];
	fac[0]=1;
    for(register int i=1;i<=sb;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[sb]=mi(fac[sb]);
    for(register int i=sb-1;i>=0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    f[0][0][0]=-1;
    for(register int i=1;i<=n;++i)
        for(register int j=0;j<=sa;++j)
            for(register int k=0;k<=sb;++k){
                f[i][j][k]=f[i-1][j][k];
                if(a[i]<=j)
                    for(register int p=0;p<b[i] && p<=k;++p)
                        f[i][j][k]-=f[i-1][j-a[i]][k-p]*mi(a[i],p)%mod*inv[p]%mod,
                        f[i][j][k]=(f[i][j][k]+mod)%mod;
            }
    for(register int i=0;i<=sa;++i)
        for(register int j=0;j<=sb;++j)
            ans+=sa*mi(mi(i),j+1)%mod*fac[j]%mod*f[n][i][j]%mod,
            ans%=mod;
    write(ans);
	return 0;
}