Luogu

分析

首先你要会 $\text{kth-max}$ 容斥:$\displaystyle\text{kth-max}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}\min(T)$ 。

当然它也可以扩展到期望:$\displaystyle E\left(\text{kth-max}(S)\right)=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}E\left(\min(T)\right)$ 。

发现这题中 $E(\min(T))$ 非常好算,考虑怎么快速求答案。

设 $f_{i,k,j}$ 表示前 $i$ 中原料,式子中的 $k$ 为 $k$ ,$\sum\limits_{t\in T}p_t=j$ 时 $\displaystyle \sum_{T\subseteq S}(-1)^{|T|-1}{|T|-1\choose k-1}$ 的值。

转移和背包类似,结合一些组合数学知识可以得到 $\large f_{i,k,j}=f_{i-1,k,j}+f_{i-1,k-1,j-p_i}-f_{i-1,k,j-p_i}$ 。

边界是 $f_{0,0,0}=0,f_{0,k,0}=-1(k\geq 1)$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline 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=10000+10;
const int mod=998244353;

int p[N],inv[N],f[15][N];

int main() {
    int n=read(),K=n-read()+1,m=read();
    for (re int i=1;i<=n;++i) p[i]=read();
    inv[0]=inv[1]=1;
    for (re int i=2;i<=m;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for (re int i=1;i<=K;++i) f[i][0]=-1;
    for (re int i=1;i<=n;++i)
        for (re int j=m;j>=p[i];--j)
            for (re int k=K;k;--k)
                f[k][j]=(f[k][j]+(f[k-1][j-p[i]]-f[k][j-p[i]]+mod)%mod)%mod;
    int ans=0;
    for (re int i=1;i<=m;++i) ans=(ans+1ll*f[K][i]*m%mod*inv[i])%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 12 PM