一，前置知识——两个计数原理
1，加法原理：完成某一个事情有n种做法，则有n种方案。
2，乘法原理：完成某一个事情有n个步骤，完成第一个步骤有a1种方法，完成第二个步骤有a2种方法，
......完成第n个步骤有an种方法，那么完成这件事情一共有（a1*a2*a3*......*an）种方案。
二，排列数
线性排列：
首先看一个简单的问题，有n个人站队，一共有n个位置，考虑顺序，一共有多少种方案数。
运用加法原理可知，在站第一个位置的时候一共有n种方案，因为第一个位置已经站了一个人了，所以
在站第二个人的时候有n-1种方案，以此类推。
再由乘法原理可知，总方案数=n*(n-1)*....*(n-n+1)=n！
这个东西记作Pnn称为全排列数。
然后扩展向一般，有n个人站队，一共只有m个位置，考虑顺序，一共有多少种方案数。
不难想到，总方案数=n*(n-1)*......*(n-m+1);
这个就是线性排列数的通式记作Pnm；
Pnm=n！/(n-m)！；
然后再介绍一些奇奇怪怪的排列
1，相异元素可重复排列 排列总数=nm
2，圆排列
从n个元素种选取出m个元素，不分首尾地排成一个圆圈的排列叫做圆排列，其排列方案数为Pnm/m;
理解：因为不分首尾了之后，会出现m个相同的圆。
3，不全相异元素的排列
如果在n个元素中有n1个元素彼此相同，有n2个元素彼此相同.....有nm个元素彼此相同
（其中n1+n2+......+nm=n) 排列公式：(n!)/(n1!*n2!*......*nm）；
三，组合数
还是从一个问题出发
有n个人站队，有m个位置，不考虑顺序（即AB和BA是同一种排列）,问一共有多少种方案数。
在组合数的基础上继续研究会发现只需要用排列公式除以一个相同的序列会出现几次即可。
一个长度为n的序列在排列数种会出现的次数为Pnn,所以我们就得到了组合数的公式
C(n,m)=P(n,m)/P(m,m)；
求出组合数的方法
1，公式法
2，Pascal公式/杨辉三角
C（n,m)=C(n-1,m-1)+C(n-1,m); 规定 C（n,0)=C(n,n)=1; 时间复杂度 O(n);
1 inline void work() 2 { 3 for(register int i=0;i<=n;++i) 4 { 5 c[i][0]=1; 6 for(register int j=1;j<=i;++j) 7 c[i][j]=c[i-1][j]+c[i-1][j-1]; 8 } 9 return; 10 }
3,Lucas定理
C（n,m)=C(n%p,m%p)*C(n/p,m/p) (modp); 时间复杂度 O(logn)