AtCoder

Luogu

分析

我不喜欢容斥,我不喜欢组合意义,我不喜欢生成函数,我也没有精神

首先 Min-Max 容斥一手

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

考虑 $E(\min(T))$ 是什么东西。它的意思是只有一个到达了 $b_i$ 的期望步数,等于没有一个到达 $b_i$ 的期望步数之和。

假设 $T=\left\{x_1,x_2,\cdots,x_m\right\}$,那么

$$ E(\min(T))=\frac{\sum_{i=1}^n a_i}{\sum_{i=1}^ma_{x_i}}\sum_{0\leq d_i< b_{x_i}}\frac{(\sum_{i=1}^m d_i)!}{\prod_{i=1}^m d_i!}\prod_{i=1}^m\left(\frac{a_{x_i}}{\sum_{j=1}^m a_{x_j}}\right)^{d_i} $$

来解释一下这个式子的意思:第一项是选中 $T$ 中的数的期望步数,第二项是一个可重集排列数,第三项是每个数被选 $d_i$ 次的概率。

假设向 $T$ 中加入了一个 $x$,则 $E(\min(T))$ 会变成

$$ E(\min(T))=\frac{\sum_{i=1}^n a_i}{x+\sum_{i=1}^ma_{x_i}}\sum_{0\leq d<b_x}\sum_{0\leq d_i< b_{x_i}}\frac{(d+\sum_{i=1}^m d_i)!}{d!\prod_{i=1}^m d_i!}\left(\frac{a_x}{a_x+\sum_{j=1}^m a_{x_j}}\right)^d\prod_{i=1}^m\left(\frac{a_{x_i}}{a_x\sum_{j=1}^m a_{x_j}}\right)^{d_i} $$

发现只有 $\sum a$ 和 $\sum d$ 发生了改变。于是可以考虑 DP:设 $dp_{i,j,k}$ 表示前 $i$ 个数,$\sum a=j$,$\sum d=k$ 时 $E(\min(T))$ 中与这两个值无关的项的期望。这些无关的项是

$$ \left(\sum_{i=1}^n a_i\right)\sum_{0\leq d_i<b_{x_i}}\frac{\prod_{i=1}^m a_{x_i}}{\prod_{i=1}^m d_i!} $$

转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去,转移要乘上一个 $-1$。

算答案就把上面这个东西代回去就好了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,a[N],b[N];
int dp[N][N][N];
int fac[N],ifac[N];

void init(int n) {
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}

int main() {
    init(400);
    n=read(); int sa=0,sb=0;
    for (int i=1;i<=n;++i) sa+=(a[i]=read()),sb+=(b[i]=read());
    dp[0][0][0]=mod-sa;
    for (int i=1;i<=n;++i) {
        memcpy(dp[i],dp[i-1],sizeof(dp[i]));
        for (int x=0,pw=1;x<b[i];++x,pw=1ll*pw*a[i]%mod)
            for (int j=a[i];j<=sa;++j)
                for (int k=x;k<=sb;++k)
                    dp[i][j][k]=(dp[i][j][k]-1ll*dp[i-1][j-a[i]][k-x]*pw%mod*ifac[x]%mod+mod)%mod;
    }
    int ans=0;
    for (int i=1;i<=sa;++i) {
        int invi=qpow(i,mod-2);
        for (int j=0,pw=invi;j<=sb;++j,pw=1ll*pw*invi%mod)
            ans=(ans+1ll*dp[n][i][j]*fac[j]%mod*pw)%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 10 月 25 日 05 : 13 PM