题目链接：http://codeforces.com/problemset/problem/577/B
题目意思：就是给出 n 个数（a1, a2, ..., an） 和 m，问能不能从这 n 个数中选出一些数（不能为空），使得这些数的总和能整除 m 。
实不相瞒，完全没想法。。。看题解，有个地方看都看不懂： n > m的情况。求助乌冬子，连带被批英语水皮 >___<。还是谢谢他啦，一步一步引导我。
貌似挺多人也有这个疑惑的。他说那个是特例优化，原谅我懒，直接摘抄吧~
首先要知道一些参数。
前缀和 Sl = a1 + a2 + ... + al-1 + al
Sr = a1 + a2 + ... + al-1 + al + al+1 + ... + ar-1 + ar
Sr - Sl = al+1 + al+2 + ...ar-1 + ar
那个翻译就是，如果有两个前缀和 mod m 相等（Sr = Sl(mod m) ），那么就有以下的前缀和向区间和的转化了。
Sr = Sl (mod m)
==> Sr - Sl = 0 (mod m)
==> a[l+1] + a[l+2] .. + a[r] = 0 (mod m)
==> Sr - Sl = 0 (mod m)
==> a[l+1] + a[l+2] .. + a[r] = 0 (mod m)
而到了 n <= m的情况， 之后就是01背包窝~~写不出来，好惨啊= =
还是用set浅显易懂。。。。
轮到我用的方法了（都是参考人的，神奇啦）
*****************************************
大体思路：保存选的数的各种组合，求出各种和的不同结果，保存在set容器中的 mods 中。当中要用到另一个set ：mods_tmp。用来保存当前处理的数a与mods中的各个和，组合出的但在原mods中没有出现的和。一轮迭代之后，将这个mods_tmp添加到mods中。这样不用下次再算嘛~~~~注意，mod m 最多只会出现 m 种结果：0， 1， 2， ..., m-1。所以不用担心超时。
顺便说说代码中为什么一开始要插入 0，因为可以只选当前输入的那个 a 嘛~~~哈哈哈·~~~
（1）这个会比（2）快（124ms）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
using namespace std; int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE int n, m;
while (scanf("%d%d", &n, &m) != EOF) { int a, r;
set<int> mods;
set<int> mods_tmp; mods.insert();
for (int i = ; i < n; i++) {
scanf("%d", &a);
for (set<int>::iterator it = mods.begin(); it != mods.end(); ++it) {
int r = (*it + a) % m;
if (r == ) {
printf("YES\n");
return ;
}
mods_tmp.insert(r);
mods_tmp.insert(a);
}
mods.insert(mods_tmp.begin(), mods_tmp.end());
mods_tmp.clear();
}
printf("NO\n");
}
return ;
}
（2）好理解点，中规中矩（218ms）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
using namespace std; int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE int n, m;
while (scanf("%d%d", &n, &m) != EOF) { int a, r;
set<int> mods;
set<int> mods_tmp; mods.insert();
for (int i = ; i < n; i++) {
scanf("%d", &a);
for (set<int>::iterator it = mods.begin(); it != mods.end(); ++it) {
int r = (*it + a) % m;
if (r == ) {
printf("YES\n");
return ;
}
mods_tmp.insert(r);
mods_tmp.insert(a);
}
mods.insert(mods_tmp.begin(), mods_tmp.end());
mods_tmp.clear();
}
printf("NO\n");
}
return ;
}