Min-Max容斥

公式：

应用：

常用来求“每次选一个数，使每个数被选的次数至少到达某个值的期望次数”

首先我们要知道对于一个局面（比如第一个数选1次，第二个数选2次）的期望步数就是这个局面的概率分之一。

证明：设期望为，概率为，那么，化简得

普遍情况：

个数，每个数有个权重，那么每一次选中第个数的概率就为，问每个数被选的次数至少到达的期望次数。

公式：

解释:

是得到一个指定集合内元素的期望时间,有重复元素的排列下,是对于集合内每个数的概率。
这个式子是怎么推出来的呢？
可以发现答案可以转化为每种状态的持续期望时间之和。那么就是状态改变的期望时间，就是每一种状态出现的概率。

例题：

E - Gachapon

题意：

个数，每个数有个权重，那么每一次选中第个数的概率就为，问每个数被选的次数至少到达的期望次数。

题解：

暴力做法就是枚举集合，然后通过上面给出的式子进行计算。

正解，考虑已经求出了一个集合的答案，现在要在这个集合里加入一个新的数

发现只要记录一下和即可转移

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=405;
const int mod=998244353;
int n,a[N],b[N],jc[N],inv[N],sum[N],f[N][N][N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return res;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
    jc[0]=jc[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=400;i++)jc[i]=jc[i-1]*i%mod;
    for(int i=2;i<=400;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=400;i++)inv[i]=inv[i]*inv[i-1]%mod;
    int s1=0,s2=0;
    f[0][0][0]=mod-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=s1;j++)
            for(int k=0;k<=s2;k++)
                f[i][j][k]=f[i-1][j][k];
        sum[0]=1;
        for(int j=1;j<b[i];j++)sum[j]=sum[j-1]*a[i]%mod;
        for(int j=0;j<b[i];j++)sum[j]=sum[j]*inv[j]%mod;
        for(int j=0;j<=s1;j++)
            for(int k=0;k<=s2;k++)
                for(int p=0;p<b[i];p++)
                    f[i][j+p][k+a[i]]=(f[i][j+p][k+a[i]]-f[i-1][j][k]*sum[p]%mod+mod)%mod;
        s1+=b[i]-1;s2+=a[i];
    }
    int ans=0;
    for(int i=0;i<=s1;i++)
        for(int j=1;j<=s2;j++)
        {
            int x=f[n][i][j]*jc[i]%mod;
            x=x*kuai(kuai(j,mod-2),i)%mod;
            ans=(ans+x*s2%mod*kuai(j,mod-2)%mod)%mod;
        }
    cout<<ans;
}