题解 | #子集#

难度可能比不上正式赛的 C .

这个样子明摆着要去算每个和为 $MM$ 的集合的贡献 . 考虑我们有一个大小为 $ss$ 的符合要求的集合 , 它最终能产生多少贡献 . 由于有 $n-sn-s$ 个数不在集合中 , 每个数都可以在 $[1,k][1,k]$ 的任意时间里选择扩充进来 , 所以答案是 $k^{n-s}k^\{n-s\}$ .

一种朴素的想法是 $d{p}_{n,m,k}dp\_\{n,m,k\}$ 为前 $nn$ 个数 , 选了 $mm$ 个数和为 $kk$ , 显然复杂度难以承担 . 但是每加入一个数 , 贡献只乘上 $\frac{1}{k}\backslash frac\{1\}\{k\}$ , 这是个常量 , 所以可以把第二维压缩掉 , 复杂度 $O(Tnm)O(Tnm)$ .

最开始我认为贡献是 $C_{n-s+k-1}^{k-1}C\_\{n-s+k-1\}^\{k-1\}$ , 后来发现所有位置是互相区分的 ...... 有没有人会对这样的贡献压缩掉一维进行 DP 啊 ......

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5000+10,MOD=1e9+7;
int T,n,m,k,_k,dp[MAXN][MAXN],a[MAXN];
int qpow(int base,int p) {
	int res=1;
	while(p) {
		if(p&1) res=res*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return res;
}
void work(void) {
	cin>>n>>m>>k; ffor(i,1,n) cin>>a[i];	
	memset(dp,0,sizeof(dp)),_k=qpow(k,MOD-2);
	dp[0][0]=qpow(k,n);
	ffor(i,1,n) {
		ffor(j,0,m) {
			dp[i][j]=dp[i-1][j];
			if(j>=a[i]) dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]]*_k)%MOD;
		}
	}
	cout<<dp[n][m]<<'\n';
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T; while(T--) work();
	return 0;
}