啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

我赛时一眼看到DP !

然后打了一个三维DP ！

考虑滚动数组，然后我就一直调啊调。。。

没调出来！！！

反倒70 -->20 了！！！

啊啊啊啊啊啊啊啊

怕 MLE 所以数组开小了点，但是没想到根本没用！开大了还能拿40！

我只有20！！！！

啊啊啊啊啊啊啊啊啊啊啊啊！

啊啊啊啊啊啊啊啊啊啊啊！

啊啊啊啊啊啊啊啊啊啊啊！

啊啊啊啊啊啊啊啊啊啊啊！！

啊啊啊啊啊啊啊啊啊啊啊！！！！

（这里安葬着一位一打比赛就掉链子的小蒟蒻

更气人的是，赛后立马就调出来了！

现在的我已经想sha人了（（（（

啊啊啊啊啊啊！！！

1. 三维DP，开小数组：20pts
2. 三维DP，开大数组：70pts
3. 压维变二维DP，避开所有坑点：100pts

AC CODE

//t2
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e3+10;
int n,t,m,p,a[N];
int dp[N][N];

signed main()
{
	scanf("%lld%lld%lld%lld",&n,&t,&m,&p);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	dp[0][0]=1;
	for(int i=1;i<=n;++i)//枚举工人 
	{
		for(int j=m;j>=0;--j)//枚举失误数 
		{
			for(int k=t;k>=0;--k)//零件 
			{
				for(int l=1/*从1开始*/; l<=k && l*a[i]<=j ;++l)//枚举此工人做多少零件
				{
					dp[j][k]+=dp[j-l*a[i]][k-l];
					dp[j][k]%=p;
				}
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<=m;++i)//从0开始
	{
//		cout<<dp[i][t]<<" ";
		ans+=dp[i][t];
		ans%=p;
	}
	printf("%lld",ans);
	
	return 0;
}

唉。。。

死吧。

题目等价于：现在有一个体积为 $Q$ 的背包，有 $N$ 个物品，第 $i$ 个物品的体积为 $a_i$ 有无限个。要求在这 $N$ 个物品中取恰好 $K$ 个物品，背包能装下的方案有多少种，答案对 $P$ 取模。

$dp[i][j][k]$ 表示前 $i$ 个物品，恰好取 $j$ 个取到体积为 $k$ 的方案数。

完全背包板子：$dp[i][j][k]=dp[i][j][k]+dp[i][j-1][k-a[i]]$

状态压缩一下，时间复杂度 $O(N \times K \times Q)$