一.鸽巢原理（抽屉原理）
1.定理：若有n个鸽巢, n+1只鸽子, 则至少有一个鸽巢里至少有两只鸽子。
2.例题：
记T为一队列，初始时为空， 现有n个总和不超过32的正整数依次入队。如果 无论这些数具体为何值，都能找到一种出队的方 式，使得存在某个时刻队列T中的数之和恰好为9， 那么n的最小值是_________。
解析：队列中的数为 ak ，设队列的前缀和为 bk ,若要使数之和恰好为九，就需要找到一个 j 与 i ，使得 bj-bi=9。bi取值范围为1-32,现将这32个数构造为集合{1,10}, {2,11}, …, {8,17}, {18,27}, {19,28},…,{23,32} ,{24},{25},{26},一共17个集合。所以至少需要 18 个数字才能让有两个在同一个集合内，满足题意。
所以，答案为 18。
3.应用：
HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖 果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜 欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存 在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序 帮忙计算一下。
思路：
可以用“隔板法”求解。找出最多的一种糖果, 把它的数量N看成N个隔板，隔成N个空间(把每个隔板的右边看成一 个空间);其 他所有糖果的数量为S。
当s<N-1时，无解，因为此时必有两个“隔板”是相邻的，不满足题意，反之，当 s>=N-1 时，成立；
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 int main() 5 { 6 ll t,n,i,j,a,sum=0,maxx; 7 scanf("%lld",&t); 8 while(t--) 9 { 10 sum=0; 11 maxx=0; 12 scanf("%lld",&n); 13 for(i=0;i<n;i++) 14 { 15 scanf("%lld",&a); 16 sum+=a; 17 if(maxx<a) 18 maxx=a; 19 } 20 if(maxx<=sum-maxx+1) 21 printf("Yes "); 22 else 23 printf("No "); 24 } 25 return 0; 26 }
推广：
鸽巢n个, 鸽子m1+m2+…+mn-n+1只, 其中 m1,m2,…,mn, n都是正整数, 则存在一个 i （i={1，2，3，，，n}） ，使得第 i 个鸽巢的数目不小于 mi
否则， 总鸽子数<=(m1-1)+(m2-1)+…+(mn-1) 与总鸽子数为m1+m2+…+mn-n+1矛盾
Erdös-Szekeres定理
定理: 在由n2+1个实数构成的序列中, 必然 含有长为n+1的单调(增或减)子序列
Ramsey定理
Ramsey定理：对于一个给定的两个整m,n>=2,则一定存在一个 最小整数r,使得用两种颜色（例如红蓝）无论给Kr的每条边如 何染色，总能找到一个红色的Km或者蓝色的Kn。显然，当 p>=r的时候，Kp也满足这个性质。
r可以看做一个有关m,n的二元函数，即r(m,n)。
基本性质：
①等价性 r(m,n)=r(n,m)
②r(2,n)=n k2较特殊 只有一条边 最小的kr为Kn
③r(m,2)=m
例题：
sum（HDU 5776）
题目大意 定一个数列，求是否存在连续子列和为m的倍数，存在输出YES，否则输出NO
思路：
预处理前缀和，一旦有两个数模m的值相同，说明中间一部分连续子列可以组成m的倍数。假设sum[1,i]%m=k，sum[1,j]%m=k,则sum[i+1,j]%m=0。
这道题相当于把n个物品放进m个抽屉里，如果n>m，那么一定会出现两个前缀和%m==k，所以n>m直接输出yes。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int vis[50005]; 4 int sum[100005]; 5 int main() 6 { 7 int t; 8 scanf("%d",&t); 9 while(t--) 10 { 11 int n,m; 12 scanf("%d %d",&n,&m); 13 memset(sum,0,sizeof(sum)); 14 memset(vis,0,sizeof(vis)); 15 for(int i=1;i<=n;i++) 16 { 17 int x; 18 scanf("%d",&x); 19 sum[i]=sum[i-1]+x; 20 vis[sum[i]%m]++; 21 } 22 if(vis[0]>=1||n>m) 23 printf("YES "); 24 else 25 { 26 int flag=0; 27 for(int i=1;i<=m;i++) 28 { 29 if(vis[i]>=2) 30 { 31 flag=1; 32 break; 33 } 34 } 35 if(flag) 36 printf("YES "); 37 else 38 printf("NO "); 39 } 40 } 41 }
二.杨辉三角 & 二项式定理
1.二项式定理
观察计算我们可以得到：
2.杨辉三角
将上图中的系数拆下来组成一个三角形就是杨辉三角了
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
......
三.容斥原理
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分.........依此类推，一直计算到所有集合相交的部分。（可以理解为就是先把所有单个集合全加一遍然后再去重）。
Venn 图：
Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits
Description
给出n个数a1,a2……an,求区间[L,R]中有多少个整数不能被其中任何一个数整除。
Input
第一行三个正整数,n,L,R。
第二行n个正整数a1,a2……an
Output
一个数，即区间[L,R]中有多少个整数不能被其中任何一个数整除。
Sample Input
2 1 1000
10 15
Sample Output
867
Data Constraint
对于30%的数据，1<=n<=10,1<=L,R<=1000
对于100%的数据，1<=n<=18,1<=L,R<=10^9
思路：容斥 ,由于n比较小，可以直接暴力dfs，看看每次选了几个数，奇数加偶数减统计答案
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll l,r,ans,t[21]; 6 int n; 7 8 ll gcd(ll a,ll b){ 9 if(b==0) return a; 10 return gcd(b,a%b); 11 } 12 13 ll lcm(ll a,ll b){ 14 return (a*b)/gcd(a,b); 15 } 16 17 void dfs(int depth,int a,ll b){ 18 if(depth>n){ 19 if(a&1) ans+=r/b-(l-1)/b; 20 else ans-=r/b-(l-1)/b; 21 return; 22 } 23 dfs(depth+1,a+1,lcm(t[depth],b)); 24 dfs(depth+1,a,b); 25 } 26 27 int main(){ 28 scanf("%d%lld%lld",&n,&l,&r); 29 for(int i=1;i<=n;i++) scanf("%lld",&t[i]); 30 dfs(1,1,1); 31 printf("%lld",ans); 32 return 0; 33 }
四.卡特兰数
思路：f[i]表示i个相同结点构成的二叉树数量。
选1个结点作为树根，选j个结点作为 树的左子树，剩余的i-j-1个结点作为树的右子树， 则左子树的形状有f[j]种，右子树的形状有f[i-j-1] 种，j可以从0取到i-1。
可以得到如下递推关系式：
f[i]= 1 if i==0 ;
∑j=0i-1 f[j]*f[i-j-1];
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 #include<vector> 8 #include<stack> 9 #include<queue> 10 #include<climits> 11 using namespace std; 12 long long a[55] = {1}; 13 int main() { 14 int n; 15 scanf("%d",&n); 16 for(int i=1; i<=n; i++) 17 for(int j=0; j<=i; j++) 18 a[i] += a[j] * a[i-j-1]; 19 printf("%lld",a[n]); 20 return 0; 21 }
五.Stirling数
第一类Stirling数
定义第一类Stirling数s(n,k)：把n个不同的元素分配到k个圆排列里，圆不能为空。问有 多少种分法？
第一类Stirling数的递推公式： s(n,k) = s(n-1, k-1) + (n-1) s(n-1,k) , 1<=k <=n ；
第二类Stirling数
第二类斯特林数S(n,m)表示的是把n个不同的小球放在m个相同的盒子里,不能有空盒子 ，问有多少中分法
递推：
s(n,m)=s(n−1,m−1)+ms(n−1,m)
容斥原理：
例题：
思路：
由于高的楼会挡住低的楼，所以这些楼首先会被划分成f+b-2个区域（除去中间最高的楼），并且左边有f-1个，右边有b-1个。
对于一个区域（假设在左边），这个区域由若干栋楼组成，并且最高的楼一定在最左边。
那么，由一个区域中的元素组成的任意一个环排列，在这个区域中都有唯一的放法，因为要把最高的元素拉到最左边。
所以，原题被简化为：将n-1个元素形成f+b-2个环排列，并将其中f-1个环放在左边的方法数。
所以答案为：S(n-1,f+b-2)*C(f+b-2,f-1)；
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxn = 2000+10; const int MOD = 1000000007; int n,f,b; ll s[maxn][maxn]; ll c[maxn][maxn]; void init(){ c[0][0] = 1; s[0][0] = 1; for(int i = 1; i < maxn; i++){ c[i][0] = c[i][i] = 1; s[i][0] = 0;s[i][i] = 1; for(int j = 1; j < i; j++){ c[i][j] = (c[i-1][j] + c[i-1][j-1])%MOD; s[i][j] = ((i-1)*s[i-1][j]+s[i-1][j-1])%MOD; } } } int main(){ int ncase; init(); cin >> ncase; while(ncase--){ scanf("%d%d%d",&n,&f,&b); if(f+b-2>n){ puts("0"); }else { ll ans = (c[f+b-2][f-1]*s[n-1][b+f-2])%MOD; printf("%d ",ans); } } return 0; }