洛谷 P4707 重返现世

洛谷 P4707 重返现世

---

k-minimax容斥

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

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

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

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

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

(sum_{Tsubseteq S}(-1)^{|T|+1-k}C_{|T|}^{k-1})
(sum_{Tsubseteq S}(-1)^{|T|+1-k}(C_{|T|-1}^{k-1}+C_{|T|-1}^{k-2}))
(sum_{Tsubseteq 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
",1ll*ans*m%mod);
	return 0;
}