洛谷 P4707 重返现世

---

k-minimax容斥

有这一个式子：\(E(\max_k(S))=\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\min(T)\)

dp。考虑怎么设状态，因为\(\min(T)=\frac{m}{\sum_{i\in T}i}\)，所以要设一维表示和；还要加一维表示当前的\(k\)。

设\(f_{i,k,j}\)表示\(S\)中加入了前\(i\)个元素，式子中的\(\sum_{T\subseteq S}(-1)^{|T|-k}C_{|T|-1}^{k-1}\)值。

考虑转移，进来一个数\(x\)可以选择加进\(T\)或不加。不加显然直接转移，\(f_{i+1,k,j}+=f_{i,k,j}\)。

如果加这个数，\(|T|\)要变成\(|T|+1\)，改写式子：

\(\sum_{T\subseteq S}(-1)^{|T|+1-k}C_{|T|}^{k-1}\)

\(\sum_{T\subseteq S}(-1)^{|T|+1-k}(C_{|T|-1}^{k-1}+C_{|T|-1}^{k-2})\)

\(\sum_{T\subseteq S}(-(-1)^{|T|-k}C_{|T|-1}^{k-1}+(-1)^{|T|-k-1}C_{|T|-1}^{k-2})\)

那么转移是\(f_{i+1,k,j}+=-f_{i,k,j-p_i}+f_{i,k-1,j-p_i}\)。

边界情况是\(f_{i,0,0}=1\)。

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 998244353

typedef long long ll;

il ll gi(){

	ll x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch))f^=ch=='-',ch=getchar();

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return f?x:-x;

}

int p[1010],f[11][10010];

il vd inc(int&a,int b){a=a+b>=mod?a+b-mod:a+b;}

il int sub(int a,int b){return a<b?a-b+mod:a-b;}

il int pow(int x,int y){

	int ret=1;

	while(y){

		if(y&1)ret=1ll*ret*x%mod;

		x=1ll*x*x%mod;y>>=1;

	}

	return ret;

}

int main(){

#ifdef XZZSB

	freopen("in.in","r",stdin);

	freopen("out.out","w",stdout);

#endif

	int n=gi(),k=n+1-gi(),m=gi();

	for(int i=1;i<=n;++i)p[i]=gi();

	f[0][0]=1;

	for(int i=1;i<=n;++i)

		for(int j=k;j;--j)

			for(int l=m;l>=p[i];--l)

				inc(f[j][l],sub(f[j-1][l-p[i]],f[j][l-p[i]]));

	int ans=0;

	for(int i=1;i<=m;++i)inc(ans,1ll*f[k][i]*pow(i,mod-2)%mod);

	printf("%d\n",1ll*ans*m%mod);

	return 0;

}