组合数

从$n$个不同元素种取出$m(m\le n)$个元素的所有不同组合的个数，叫做从$n$个不同元素种取出$m$个元素的组合数，用符号$C_n^m$表示。¹

基本公式

$${\mathrm{C}}_n^m=\frac{{\mathrm{A}}_n^m}{{\mathrm{A}}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},n,m\in {\mathbb{N}}^{\ast },\text{并且}m\le n$$$${\mathrm{C}}_n^0={\mathrm{C}}_n^n=1$$

性质

$${\mathrm{C}}_n^m={\mathrm{C}}_n^{n-m}$$$${\mathrm{C}}_n^m={\mathrm{C}}_{n-1}^m+{\mathrm{C}}_{n-1}^{m-1}$$

很好理解， 第一个式子可以看作选取之前没有选取的元素的方案就等于之前的方案，因为它们之间是一一对应的。 第二个式子可以看作把当前选取方案拆分成两部分，一部分含有特定元素，一部分不含特定元素，就能将当前方案数不重不漏地分好。

求和公式

$${\mathrm{C}}_n^0+{\mathrm{C}}_n^1+{\mathrm{C}}_n^2+\cdots +{\mathrm{C}}_n^n=2^n$$

证明：

当$n=1$时，${\mathrm{C}}_1^0+{\mathrm{C}}_1^1=2=2^1$。 假设$n=k(k\in {\mathbb{N}}^{\ast })$时成立，即

$$\sum _{i=0}^k{\mathrm{C}}_k^i=2^n$$

成立 当$n=k+1$时，

$$\begin{array}{rl}& {\mathrm{C}}_{k+1}^0+{\mathrm{C}}_{k+1}^1+{\mathrm{C}}_{k+1}^2+\cdots +{\mathrm{C}}_{k+1}^k+{\mathrm{C}}_{k+1}^{k+1}\\ =& {\mathrm{C}}_{k+1}^0+({\mathrm{C}}_k^0+{\mathrm{C}}_k^1)+({\mathrm{C}}_k^1+{\mathrm{C}}_k^2)+\cdots +({\mathrm{C}}_k^{k-1}+{\mathrm{C}}_k^k)+{\mathrm{C}}_{k+1}^{k+1}\\ =& ({\mathrm{C}}_k^0+{\mathrm{C}}_k^1+{\mathrm{C}}_k^2+\cdots +{\mathrm{C}}_k^k)+({\mathrm{C}}_k^0+{\mathrm{C}}_k^1+{\mathrm{C}}_k^2+\cdots +{\mathrm{C}}_k^k)\\ =& 2\times 2^k\\ =& 2^{k+1}\end{array}$$

所以等式对$n\in {\mathbb{N}}^{\ast }$都成立。

---

求解方法

求 $C_a^{b}modp$

递推式求解 $O(n^2)$

$$\begin{gathered} 1\le n\le 10000, \\ 1\le b\le a\le 2000 \end{gathered}$$

直接应用 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$

//Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2010,mod = 1e9+7;
int C[N][N];
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(j==0) C[i][j] = 1;
            else{
                C[i][j] = (C[i-1][j-1]+C[i-1][j]) % mod;
            }
        }
    }
}
int main(){
    init();
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        cout<<C[a][b]<<endl;
    }
    return 0;
}

预处理阶乘及其逆元 $O(a\ast log(p))$

$$\begin{gathered} 1\le n\le 10000, \\ 1\le b\le a\le {10}^5 \end{gathered}$$

原理:

$$C_a^b=\frac{a!}{b!(a-b)!}=a!b{!}^{-1}(a-b){!}^{-1}$$

因 $p$ 为质数,所以逆元可用费马小定理求

//Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100010, mod =1e9+7;
int fact[N],invfact[N];
ll qpow(ll a,int b,int p){ //因为a会被算平方所以要用ll否则可能会溢出
    ll res=1;
    while(b){
        if(b&1) res = res * a % p;
        b>>=1;
        a = a*a % p;
    }
    return res;
}

int main(){
    fact[0] = invfact[0] = 1;
    for(int i=1;i<N;i++){ //递推阶乘及逆元
        fact[i] = (ll)fact[i-1] * i % mod;
        invfact[i] = (ll)invfact[i-1] * qpow(i,mod - 2 ,mod) % mod;
    }
    int n;
    scanf("%d",&n);
    while(n--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",(ll)fact[a]%mod * invfact[b]%mod * invfact[a-b]%mod); //查表输出答案
    }
    return 0;
}

Lucas定理求模意义下组合数 $O(lo{g}_{p}N\ast (p+logp))$

$$\begin{gathered} 1\le n\le 20, \\ 1\le b\le a\le {10}^{18}, \\ 1\le p\le {10}^5 \end{gathered}$$

Lucas 定理是同余理论中的一个很重要的定理，用于组合数取模。常常使用在问题的结果需要对某个数据取模，$n,m$ 很大，达到 ${10}^{15}$ 以上，但是 $p$ 在 ${10}^9$ 以内。一般来说最好的效果实在 ${10}^5$ 以内。

$$C_m^n=C_{mmodp}^{nmodp}\cdot C_{\lfloor \frac{m}{p}\rfloor }^{\lfloor \frac{n}{p}\rfloor }(modp)$$

//Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int qpow(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
LL C(LL a, LL b, int p)
{
    if(b > a) return 0;
    if(b > a - b) b = a - b;
    LL x = 1, y = 1;
    for(int i = 0; i < b; i++)
    {
        x = x * (a - i) % p;
        y = y * (i + 1) % p;
    }
    return x * qpow(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; //递归求解, 多次使用 Lucas 定理加快速度
}
int main(){
    int n;
    cin >> n;

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a+b, b, p) << endl;
    }
    return 0;
}

Lucas 定理的证明

² 考虑 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{n})modp}$ 的取值，注意到 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{n})=\frac{p!}{n!(p-n)!}}$，分子的质因子分解中 $p$ 次项恰为 $1$，因此只有当 $n=0$ 或 $n=p$ 的时候 $n!(p-n)!$ 的质因子分解中含有 $p$，因此 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{n})modp=[n=0\vee n=p]}$。进而我们可以得出

$$\begin{array}{}\text{(3)}& (a+b{)}^p& =\sum _{n=0}^p(\genfrac{}{}{0ex}{}{p}{n})a^n{b}^{p-n}\text{(4)}& & \equiv \sum _{n=0}^p[n=0\vee n=p]a^n{b}^{p-n}\text{(5)}& & \equiv a^p+b^p(\mathrm{mod}p)\end{array}$$

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 $f^p(x)=(a{x}^n+b{x}^m{)}^{p}modp$ 的结果

$$\begin{array}{}\text{(6)}& (a{x}^n+b{x}^m{)}^p& \equiv a^p{x}^{pn}+b^p{x}^{pm}\text{(7)}& & \equiv a{x}^{pn}+b{x}^{pm}\text{(8)}& & \equiv f(x^p)\end{array}$$

考虑二项式 $(1+x{)}^{n}modp$，那么 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{m})}$ 就是求其在 $x^m$ 次项的取值。使用上述引理，我们可以得到

$$\begin{array}{}\text{(9)}& (1+x{)}^n& \equiv (1+x{)}^{p\lfloor n/p\rfloor }(1+x{)}^{nmodp}\text{(10)}& & \equiv (1+x^p{)}^{\lfloor n/p\rfloor }(1+x{)}^{nmodp}\end{array}$$

注意前者只有在 $p$ 的倍数位置才有取值，而后者最高次项为 $nmodp\le p-1$，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 $p$ 的倍数次项，后者部分取剩余项，即 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{m})modp=(\genfrac{}{}{0ex}{}{\lfloor n/p\rfloor }{\lfloor m/p\rfloor })\cdot (\genfrac{}{}{0ex}{}{nmodp}{mmodp})modp}$。

参考

• [1] 组合 - 维基百科，自由的百科全书

• [2] 卢卡斯定理 - OI Wiki