AT_agc038_e [AGC038E] Gachapon 题解

· · 题解

难得的 \mathbf{\min-\max} 容斥题。

题目指路。

题意

有一随机数生成器，每次生成 [0,n-1] 的整数，生成 i 的概率为 \dfrac {a_i} A，其中 A=\sum\limits_{i=0}^{n-1}a_i。当所有 i\in[0,n-1] 都生成了至少 b_i 次时，停止生成。求期望生成次数。

思路

题面里的所有都出现多少次很不好解决，考虑 \min-\max 容斥，我们有下式：

【\mathbf{\min-\max} 容斥】 E(\max S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}E(\min T)。

则答案变成：

\sum\limits_{T\subseteq\{0,1,\cdots,n-1\}}(-1)^{|T|-1}E(T)

其中 E(T) 表示 T 中至少有一个元素 i 生成不小于 b_i 次的期望次数。但这还是不好算，还要再推一推。记 t 为结束时间，把期望拆成概率，得到：

P(t=1)+2P(t=2)+3P(t=3)+\cdots

加法交换律一下：

(P(t=1)+P(t=2)+\cdots)+(P(t=2)+\cdots)+\cdots

整理：

P(t\ge1)+P(t\ge2)+\cdots

该式的实际意义为，第 0 轮所有元素 i 选到次数小于 b_i 的概率，加第 1 轮的概率，加第 2 轮，一直加下去。

但是这个仅仅是在集合内选的期望。我们还要考虑随机生成到集合外。也就是说，上面这个式子还要再乘以随机生成到集合内的期望次数，即概率的倒数，才是 E(T)。设 A=\sum\limits_{i=0}^{n-1}a_i,B=\sum\limits_{i=0}^{n-1}b_i，则系数为 \dfrac A{\sum\limits_{i\in T} a_i}。

接下来计算第 0 轮所有元素 i 选到次数小于 b_i 的概率，加第 1 轮的概率，加第 2 轮，一直加下去的值。我们考虑计算第 k 轮的贡献。枚举每个数的出现次数 c_0,c_1\cdots c_{n-1}，满足 \sum\limits_{i\in T} c_i=k,c_i<b_i，则方案数为多重组合数，概率是生成每个数的概率乘在一起，贡献为二者相乘。即：

\left(\dfrac{k!}{\prod\limits_{i\in T}c_i!}\right)\left(\prod\limits_{i\in T}(\dfrac{a_i}{\sum\limits_{j\in T} a_j})^{c_i}\right)

整理得：

\dfrac{k!}{(\sum\limits_{j\in T} a_j)^k}\prod\limits_{i\in T}\dfrac{a_i^{c_i}}{c_i!}

最终答案为：

A\sum\limits_{T\subseteq\{0,1,\cdots,n-1\}}(-1)^{|T|-1}\sum\limits_{k}\dfrac{k!}{(\sum\limits_{i\in T} a_i)^{k+1}}\prod\limits_{i\in T}\dfrac{a_i^{c_i}}{c_i!}

设 dp(i,j,k) 表示考虑到第 i 个，所选的 a_i 的和为 j，c_i 的和为 k 的贡献，做一遍带容斥系数的背包就好了。

具体地，转移为：

dp(i,j,k)=dp(i-1,j,k)-\sum\limits_{t=0}^{\min\{b_i-1,k\}}dp(i-1,j-a_i,k-t)\dfrac{a_i^t}{t!}

由于带容斥系数，初值 dp(-1,0,0)=-1，其余为 0。

最后答案为 A\sum\limits_{j=0}^A\sum\limits_{k=0}^B\dfrac{dp(n,j,k)}{j^{k+1}}k!

时间复杂度 O(nAB)，代码把下标平移到了 1\sim n。

代码

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MOD=998244353,MAXN=401;
int n,a[MAXN],b[MAXN],A,B;
int fact[MAXN],invf[MAXN],inv[MAXN];
int po[MAXN][MAXN+10];
int dp[2][MAXN][MAXN];
inline ll qpow(ll base,int expo){
    ll res(1);
    while(expo){
        (expo&1)&&(res=res*base%MOD);
        base=base*base%MOD,expo>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    fact[0]=fact[1]=invf[0]=invf[1]=inv[1]=1;
    F(i,2,400) inv[i]=MOD-MOD/i*1ll*inv[MOD%i]%MOD,fact[i]=fact[i-1]*1ll*i%MOD,invf[i]=invf[i-1]*1ll*inv[i]%MOD;
    F(i,1,400){
        po[i][0]=1;
        F(j,1,410) po[i][j]=po[i][j-1]*1ll*i%MOD;
    }
    cin>>n;
    F(i,1,n) cin>>a[i]>>b[i],A+=a[i],B+=b[i];
    dp[0][0][0]=MOD-1;
    F(i,1,n){
        int now(i&1),pre(now^1);
        F(j,0,A) F(k,0,B){
            int&qwq(dp[now][j][k]);
            qwq=dp[pre][j][k];
            if(j<a[i]) continue;
            F(t,0,min(b[i]-1,k)) qwq=(qwq-dp[pre][j-a[i]][k-t]*1ll*po[a[i]][t]%MOD*invf[t])%MOD+MOD;
        }
    }
    int ans(0);
    F(i,0,A) F(j,0,B) ans=(ans+dp[n&1][i][j]*qpow(inv[i],j+1)%MOD*fact[j])%MOD;
    cout<<(ans+MOD)*1ll*A%MOD;
    return 0;
}