算法提高篇--数学基础（六）：组合数学（1）

不学不知道，算法真奇妙。又到了将“算法”刻到骨子里的时刻，今天为大家带来的是数学基础的第六讲——组合数学（1）。

1、排列组合

排列组合是组合数学中的基础。其研究的中心问题就是给定要求的排列和组合求可能出现的情况总数。

排列：

从n个不同的元素中，任取m（m≤n）个元素按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列；所有满足以上条件的排列个数，叫做从n个不同元素中取出m个元素的排列数，用符号

表示（老版本的书也有用P而不是A表示的）。

其计算公式为： = n(n-1)...(n-m+1) = n!/(n-m)!

可以形象的理解为n个人中选m个人来排队，第1个位置有n种可能，第2个位置在第一个位置选中一个人后只剩下(n-1)种可能，以此类推，最后第m个位置有(n-m+1)种可能。即排列是有先后顺序关系的，即“ABC”和“BAC”是不同的两种排列。

特殊地，从n中选择n个来排队则构成了全排列，其排列数为n!。

组合：

排列是有先后次序关系的，而组合是不考虑顺序的，即“ABC”和“BAC”是属于同一种组合。因此，我们定义组合为从n个不同的元素中，任取m个元素组成一个集合，叫做从n个不同元素中取出m个元素的一个组合；满足以上条件的组合个数，叫做从n个不同元素中取出m个元素的组合数，用符号表示。

其计算公式为：= /m! = n! /[m!(n-m)!]

现代数学多用 来表示。

排列组合常用技巧：

1）、捆绑法：

9个人排成一排，A和B要站在一起，有多少种方案？

答：把A和B捆绑在一起当成一个人（穿一条内裤），现在就把问题转化为8条内裤（个人）的全排列问题了，即A(8,8)，又对于A和B，他们之间也有两种排列方式，即A(2,2)，因此，最终的结果是2!*8!

2）、隔板法：

9个人排成一排，A和B闹矛盾不能站在一起，有多少种排队方案？

答：先将除A和B外的7个人排成一排，然后把这7个人当成是隔板，则A和B有8个空位可以插入，在这8个空位中选两个给A、B即可。即：A(7,7)*A(8,2) = 7!*8!/6!

二项式定理：

二项式定理阐明了一个展开式的系数：

借助组合数其实可以很容易记住二项式定理的展开式，即对于每一项，其实都是n次项，其不同就在于多少个a和多少个b，即对应任意一项，除开系数之外可以表示为a^(n-i)*b^i。系数其实就是组合数，即n次中，a为(n-i)次、b为i次的组合数。即系数为：

。有了这个知识，我们可以迅速解决下面一道真题。

3、小试牛刀

一本通1648题。

本题是二项式定理的直接应用，对应a和b要与x和y一样，分别用快速幂求得n次方和m次方作为系数的因数，组合数求的是k中取n的集合数量。这里可以用递推式求得，为更方便大家理解，这里用杨辉三角来展现二项式展开后的系数。

通过对比，我们发现杨辉三角的数值对应的就是二项式展开后的系数。进一步观察将杨辉三角按照特定的方式存储后如下图所示：

发现下一行的数值，可以由上一行递推得到，即定义f[i][j]为第i行第j列的数值，则f[i][j] = f[i-1][j-1] + f[i-1][j]。由此，我们可以推导得出对应k次方的二项式的系数，对应的就是杨辉三角第k+1行的数值；而列数则是跟n或m的值有关，我们举m的例子，通过比较上述两图，对应第二项为m次方的系数，在杨辉三角对应的是第m+1行。即x^ny^m的系数为f[k+1][m+1]。此外，我们还有常数项的n次方和m次方作为最终系数的因数，这里需要用到快速幂。综上，我们利用递推和快速幂找到正解。参考代码如下：

#include<bits/stdc++.h> using namespace std;const int mod = 10007;const int N = 1005;typedef long long ll;int c[N][N];/**快速幂 */ll quickPow(ll x,ll y){  ll res=1,base = x;  while(y){    if(y&1){      res = (res*base)%mod;    }    base *= base;    base %= mod;    y = y>>1;  }  return res;} /**递推求组合 */ll getC(int n,int m){//对应k次方时，取getC(k+1,k-n+1) .   c[1][1] = 1;  for(int i=2;i<=n;++i){        for(int j=1;j<=i;++j){      c[i][j] = c[i-1][j]%mod+ c[i-1][j-1]%mod;    }      }    return c[n][m]%mod;}int main(){  int a,b,k,n,m;  scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);  ll res = 1;  res = getC(k+1,m+1)*quickPow(a,n)%mod*quickPow(b,m)%mod;  printf("%lld\n",res);  return 0;}

4、卢卡斯定理应用

卢卡斯(Lucas)定理是用来求 c(n,m) mod p，其中p为素数。卢卡斯定理：我们令n=sp+q，m = tp+r。（0≤q,r≤p-1），则有c(n,m) = c(sp+q,tp+q) = c(s,t)*c(q,r)(% p)。即c(n,m) = c(n/p,m/p)*c(n%p,m%p)(% p)。

一本通1650则是利用卢卡斯定理求解问题的模板题：

数据范围很大，现在常规的解法肯定爆，应用lucas定理，则为此题正解。参考代码如下：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll mod;inline ll read(){    ll res=0;    bool flag=0;    char c=getchar();    while(c<'0'||c>'9')    {        flag|=(c=='-');         c=getchar();    }    while(c>='0'&&c<='9')    {        res=(res<<3)+(res<<1)+(c^48);         c=getchar();    }    return (flag)?(-res):(res);}/**快速幂，求a^b */inline ll quickPowWithMod(ll a,ll b){    ll res=1;    while(b)    {        if(b&1) res=res*a%mod;        a=a*a%mod;        b>>=1;    }    return res;}/**用阶乘求组合数 */inline ll calbyFac(ll n,ll m){    if(n<m) return 0;    if(n==m) return 1;    m=min(m,n-m);//利用对称性     ll a=1,b=1;    for(ll i=n-m+1;i<=n;i++) a=a*i%mod;//求n(n-1)*...*(n-m+1)     for(ll i=2;i<=m;i++) b=b*i%mod;//求m!    return a*quickPowWithMod(b,mod-2)%mod;//运用欧拉定理求逆元 ≡(a/b)%mod }/**卢卡斯定理 */inline ll lukas(ll n,ll m){    ll res=1;    while(n&&m)    {        res=res*calbyFac(n%mod,m%mod)%mod;        n/=mod;        m/=mod;    }    return res;}int main(){    ll T;    T = read();    while(T--)    {        ll n=read(),m=read();        mod=read();        printf("%lld\n",lukas(n,m));    }    return 0;}

5、小结

我们稍微小结一下在NOIP中要掌握的几种求组合数的方法：

1）、利用杨辉三角递推式，这种方法的优点是对于模数没有特殊要求（不需要是素数）。其复杂度为O(n²)，因此对n<=5000时，是可以使用的，超过了则会爆TIL。

2）、利用组合数的通项公式，其复杂度为O(n)，因此n≤1e6时，可在1s内完成求解，要求是模数p必须为素数，利用逆元，将除法转化为乘法来处理。

3）、利用lukas定理快速求组合数，要求模数P是素数，其时间复杂度为O(logn)，这是n满足≤2e9。即int类型范围内适用。

本讲，我们主要介绍了排列组合，以及如何求组合数，更多的组合数学相关知识将在以后再跟大家一起来学习，谢谢大家的时间。