Description：

有 $n$ 个程序员，每个程序员可以写若干行代码，第 $i$ 个程序员每行里会有 $a_i$ 个 $bug$ ，现在要完成一个恰好 $m$ 行的代码且总 $bug$ 数量不能超过 $b$ ，求有多少种完成方案。

$1\le n,m \le 500$

Solution：

考虑每个程序员为一个阶段，决策时需要知道当前已完成的行数与 $bug$ 数， $f(i,j,k)$ 表示前 $i$ 个程序员共写了 $j$ 行代码，产生 $bug$ 数为 $k$ 的方案数 $\begin{align}f(i,j,k) = \sum^j_{x=0} f(i−1,j−x,k−a_i\times x) \end{align}$ 注意到这其实是个完全背包问题，考虑改写转移方程进行优化 $f(i,j,k) = f(i−1,j,k) +f(i,j−1,k−a_i) $ 。滚动数组优化空间

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,b,MOD;

#define MAXN 510

int a[MAXN];

int f[2][MAXN][MAXN];

int main()

{

	scanf("%d%d%d%d",&n,&m,&b,&MOD);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	int cur = 0;

	f[0][0][0] = 1;

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

	{

		cur = cur ^ 1;

		for(int j = 0;j <= m;++j)

		{

			for(int k = 0;k <= b;++k)

			{

				f[cur][j][k] = f[cur ^ 1][j][k];

				if(k >= a[i])f[cur][j][k] = (f[cur][j][k] + f[cur][j - 1][k - a[i]]) % MOD;

			}

		}

	}

	int ans = 0;

	for(int i = 0;i <= b;++i)

	{

		ans = (ans + f[cur][m][i]) % MOD;

	}

	cout << ans << endl;

	return 0;

}