codeforces #302Div1 A

对于我这样的弱者就需要一道一道简单的题来慢慢补了。
看懂题意很重要：
又一次被自己的英语吓哭了，做了两天发现题目看错，结果样例都对了，
硬是过不了；
给 n,m,b,mod;
在给n 个数 a[i]，每个代码猴子，写1行代码会产生的bugs
有 v[1]+v[2]+v[3]+.....+v[n] N 只代码猴子写的行数要等于m
求有多少中方案,结果% MOD；
（总之，我的描述估计只有自己看懂了

解析：三维,DP[I][J][K] 代表：做到第i人，产生k个bug 并且写了 j行，
转移一下就好了
dp[i][j][k]=dp[i-1][j][k];
dp[i][j][k]+=dp[i-1][j-1][k-a[i]];k>=a[i];
dp[i][j][k]%=mod;

然后：三维500500500存不下，滚动数组

include

include <string.h>

include

define N 123456

define inf 0x3f3f3f

using namespace std;
typedef long long ll;

int n,m,b,mod;

int a[555];
ll dp[2][505][505];

int main()
{
cin>>n>>m>>b>>mod;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);

dp[0][0][0]=1;

int it=0;
for (int i=1;i<=n;i++)
{
  it^=1;
  for (int j=0;j<=m;j++)
  for (int k=0;k<=b;k++){
  dp[it][j][k]=dp[it^1][j][k];
  if (j>0&&k>=a[i]) dp[it][j][k]=(dp[it][j][k]+dp[it][j-1][k-a[i]])%mod;
  }
}
ll ans=0;
for (int i=0;i<=b;i++) ans=(ans+dp[it][m][i])%mod;
cout<<ans;
return 0;

}