题
题意
给你n（1 ≤ n ≤ 106）个数a1..an（0 ≤ ai ≤ 109），再给你m（ 2 ≤ m ≤ 103）如果n个数的子集的和可以被m整除，则输出YES，否则NO。
分析
分两种情况：
当n＞m时，s[i]表示a[i]前缀和，s[i]%m的取值为0到m-1，由抽屉原理/鸽巢原理可知，s[i]一定有重复的，假如重复的是s[l]和s[r]，那么s[r]-s[l]也就是l 1到r这些数加起来就是m 的倍数。故答案为YES。
当n≤m时，我们用dp[i][j]==1表示前i个数可以得到对m取余为j的子集，每次读入一个a，dp[i][a%m]=1;dp[i][j]=max(dp[i-1][j],dp[i-1][(m j-a[i]%m)%m])（j!=a%m,0≤j<m），也就是多了第i张钱能否得到对m取余为j的价格。一旦得到dp[i][0]==1，答案就是YES就不用继续算了。但是这样太浪费空间了，也开不了那么大数组，i最大为106。只要保存上一次的和这一次的就够了。
另一种是直接推，根据之前可得到的余数推出这一轮可得到的余数。
代码
dp代码
代码语言：javascript复制#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a;
int dp[2][1005];
int main()
{
scanf("%d%d",&n,&m);
if(n>m)dp[0][0]=1;
else
for(int i=1; i<=n; i )
{
for(int j=0; j<m; j )dp[1][j]=0;
scanf("%d",&a);
dp[1][a%m]=1;
for(int j=0; j<m; j )
{
if(dp[1][0])break;
if(j!=a%m)
dp[1][j]=max(dp[0][j],dp[0][(m j-a%m)%m]);
}
for(int j=0; j<m; j )
dp[0][j]=dp[1][j];
}
if(dp[0][0]) printf("YES");
else printf("NO");
return 0;
}另一种代码
思路是mark[i]标记当前所有数余数i能否出现，t[i]记录的之前余数i能否出现。
代码语言：javascript复制#include<cstdio>
#include<cstring>
int n,m;
int a;
int mark[1005],t[1005];
int main()
{
scanf("%d%d",&n,&m);
if(n>m)t[0]=1;
else
while(n--)
{
scanf("%d",&a);
memset(mark,0,sizeof(mark));
mark[a%m]=1;
for(int i=0; i<m; i )
{
if(t[0]) break;
if(t[i]) mark[(a%m i)%m]=1;
//如果之前可得到%m=i的价格，那现在就可得到(a%m i)%m的价格
}
for(int i=0; i<m; i )
{
if(t[i]==0) t[i]=mark[i];
//保存这一轮的。不能合并到上面一起写
}
}
if(t[0]) printf("YESn");
else printf("NOn");
return 0;
}
