# command_block 的博客

### 题解 P4707 【重返现世】

posted on 2019-06-29 19:59:41 | under 题解 |

$ANS=\sum\limits_{T∈S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))$

$E(min(T))$和$\sum\limits_{i∈T}p_i$直接相关。

$f[i][j+1][k+p[i]]+=f[i-1][j][k];$

$\sum(-1)^{|T|-k-1}\dbinom{|T|}{k-2}+\sum(-1)^{|T|-k+1}\dbinom{|T|-1}{k-1}$

$=f[i-1][j][k-1]-f[i-1][j][k]$,皆大欢喜!

Code:

#include<algorithm>
#include<cstdio>
#include<map>
#define mod 998244353
#define MaxM 10050
#define mod 998244353
using namespace std;
long long f[MaxM][15],ans;
int n,kk,m,p[MaxM];
long long powM(long long a,long long t)
{
long long ans=1;
while(t){
if (t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}return ans;
}
int main()
{
scanf("%d%d%d",&n,&kk,&m);kk=n-kk+1;
for (int i=1;i<=n;i++)scanf("%d",&p[i]);
f[0][0]=1;
for (int i=1;i<=n;i++)
if (p[i])
for (int j=m-p[i];j>=0;j--)
for (int k=kk;k;k--)
f[j+p[i]][k]=(f[j+p[i]][k]+f[j][k-1]-f[j][k])%998244353;
for (int j=1;j<=m;j++)
ans=(ans+f[j][kk]*m%mod*powM(j,mod-2))%mod;
printf("%lld",(ans+mod)%mod);
return 0;
}