这章没有什么算法可言，单纯的你懂了原理后会不会运用（反正我基本没怎么用过￣ 3￣）
有366人，那么至少有两人同一天出生（好孩子就不要在意闰年啦(￣▽￣")）
有13人，那么至少有两人同一月出生
这就是抽屉原理
抽屉原理：把n+1个物品放到n个抽屉里，那么至少有两个物品在同一个抽屉里
鸽巢原理：把n+1个鸽子放到n个鸽巢里，那么至少有两个鸽子在同一个鸽巢里
球盒原理：把n+1个小球放到n个球盒里，那么至少有两个小球在同一个球盒里
（你看，我都帮你们解释里一遍(≧︶≦*)）
其实抽屉原理有两个
第一抽屉原理
原理1： 把多于n+k个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
原理2 ：把多于mn(m乘以n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
第二抽屉原理
把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体(例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。
原理懂了，但是你会运用吗？
来看这一题
cf 577B
http://codeforces.com/problemset/problem/577/B
Modulo Sum
给你一个序列a1,a2...an，再给你一个数字m
问你能不能从中选出几个数，把他们相加，令这个和能够整除m
能就是输出YES，不能就输出NO
不知道你有木有思路(O ° ω ° O )
正常讲肯定是dp咯，加一点剪枝，勉强卡过了（因为CF上面都是单组数据，多组可能就超时了）
AC代码：
#include<cstdio>
#include<cstring>
const int N = (int)1e6 + ;
int n, m;
int a[N];
bool dp[][];//滚动数组
bool work(){
dp[][a[]] = true;
for(int i = ; i < n; i ++){
memset(dp[i & ], , sizeof(bool)*);
dp[i & ][a[i]] = true;
for(int j = ; j < m; j ++){
if(dp[(i-) & ][j]){
dp[i & ][(j + a[i]) % m] = true;
dp[i & ][j] = true;
}
}
if(dp[i & ][]) return true;
}
return dp[(n-) & ][];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = ; i < n; i ++){
scanf("%d", &a[i]);
a[i] %= m;
}
puts(work() ? "YES" : "NO");
}
其实这题的n虽然范围大，但是我们可以加一个判断，n>m的话，必然输出YES
为什么？根据抽屉原理呗
先求前缀和求余m，
如果有m+1个数，那么就会产生m+1个前缀和，求余完m，就会有m+1个余数
我们知道求余完m会产生0~m-1总共m个余数
那么根据抽屉原理，至少有两个相同的余数
那么他们之间的数的和求余m就肯定是0，所以n>m的话，必然输出YES
比如
取两个下标i和j（i < j）
(a1+a2+...+ai) % m = k
(a1+a2+...+aj) % m = k
那么(ai+...+aj) %m = 0
所以问题解决啦
AC代码：
#include<cstdio>
#include<cstring>
const int N = (int)1e6 + ;
int n, m;
int a[N];
bool dp[][];//滚动数组
bool work(){
if(n > m) return true;//多加这一句，TLE的代码说不定就能AC
dp[][a[]] = true;
for(int i = ; i < n; i ++){
memset(dp[i & ], , sizeof(bool)*);
dp[i & ][a[i]] = true;
for(int j = ; j < m; j ++){
if(dp[(i-) & ][j]){
dp[i & ][(j + a[i]) % m] = true;
dp[i & ][j] = true;
}
}
if(dp[i & ][]) return true;
}
return dp[(n-) & ][];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = ; i < n; i ++){
scanf("%d", &a[i]);
a[i] %= m;
}
puts(work() ? "YES" : "NO");
}
这个原理懂了，一定要学会用，要不然碰上别的题目一样不会（又在黑自己。。。(￣▽￣")）