解法一：普通动态规划（二维数组）

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,K=1e3+10,mod=1e8;
int f[N][K],a[N];
int main()
{
    //freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k-1;j++)
		{
			f[i][j]=(  f[i-1][j]   +  f[i-1][((j-a[i])%k+k)%k]   )  % mod;
		}
    printf("%d\n",(f[n][0]-1+mod)% mod);
    return 0;
}

解法二：滚动数组优化

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,K=1e3+10,mod=1e8;
int f[2][K],a[N];
int main()
{
    //freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	memset(f,0,sizeof(f));
	f[0][0]=1;
    int  t=0;
	for(int i=1;i<=n;i++)
    {
        t=t^1;
        memset(f[t],0,sizeof(f[t]));

		for(int j=0;j<=k-1;j++)
		{
			f[t][j]=(  f[t^1][j]   +  f[t^1][((j-a[i])%k+k)%k]   )  % mod;
		}
    }
    printf("%d\n",(f[t][0]-1+mod)% mod);
    return 0;
}

原始代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,K=1e3+10,mod=1e8;
int f[N][K],a[N];
int main()
{
    //freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k-1;j++)
		{
			f[i][j]=(  f[i-1][j]   +  f[i-1][((j-a[i])%k+k)%k]   )  % mod;
		}
    printf("%d\n",(f[n][0]-1+mod)% mod);
    return 0;
}

滚动数组代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,K=1e3+10,mod=1e8;
int f[2][K],a[N];
int main()
{
    //freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	memset(f,0,sizeof(f));
	f[0][0]=1;
    int  t=0;
	for(int i=1;i<=n;i++)
    {
        t=t^1;
        memset(f[t],0,sizeof(f[t]));

		for(int j=0;j<=k-1;j++)
		{
			f[t][j]=(  f[t^1][j]   +  f[t^1][((j-a[i])%k+k)%k]   )  % mod;
		}
    }
    printf("%d\n",(f[t][0]-1+mod)% mod);
    return 0;
}