$\Huge\color{orchid}{点击此处获取更多干货}$
$\Large\color{black}{上一节在此}$

上一节介绍了组合数$C_n^m$的计算公式和从公式入手的直接计算方法，本节将介绍关于组合数的两个重要定理。第一个定理来源于二项式$x+1$的指数展开以及杨辉三角，它的表达式为$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$。本节首先介绍，杨辉三角是什么，以及它如何与组合数互相联系起来。

杨辉三角的历史渊源可以自己去了解，不属于本帖的重点讨论内容，下图中的三角形数表就是杨辉三角的一部分。

从中可以得出以下结论：
1. 每一行的第一个和最后一个都是1（如紫色方框所示）
2. 每一个数都由其正上方和左上方的数累加而得（如蓝色圈中的10，是由上一行红色圈中的4和6累加得到）

而结合$(x+1)^n$的展开式$C_n^0*x^0+C_n^1*x^1+…+C_n^{n-1}*x^{n-1}+C_n^n*x^n$即$\prod_{i=0}^{n}C_n^i*x^i$，将组合数公式代入计算后得知，其中每一行的$n$个数，都和$C_n^0,C_n^1,…,C_n^n$一一对应，可以利用这样的对应关系，通过构造杨辉三角来求得某一确定的$C_n^m$

size_t combine(size_t n, size_t m, size_t p) {
    if (n < 2) return 1;
    vector<vector<size_t>> cb = {               //先把三角形顶部构造好
        {1}, {1, 1}
    };
    for (int i = 2; i <= n; i++) {              //然后按照上述定理构造完n层
        cb.push_back(vector<size_t>(i + 1, 1)); //两端一定是1
        for (int j = 1; j < i; j++) {           //除了两端之外，其余部分都要累加
            cb[i][j] = (cb[i - 1][j] + cb[i - 1][j - 1]) % p;
        }
    }
    return cb[n][m];
}

第二个定理也许只有数学系的才会知道，不过本帖可将其作为补充。如果将组合数计算函数$\text{combine}$的参数$m,n,p$利用起来，将$m,n$转换成为$p$进制下的$\overline{a_0a_1a_2…a_n}$和$\overline{b_0b_1b_2…b_n}$（其中$a_i,b_i$是转换后各数位上的数码，那么$C_n^m\%p=(\prod_{i=0}^{n}C_{b_i}^{a_i})\%p$。考虑到$a_n,b_n$分别相当于$m\%p,n\%p$，而$\overline{a_0a_1a_2…a_{n-1}}$和$\overline{b_0b_1b_2…b_{n-1}}$分别相当于$m/p,n/p$，该定理又可以写成同余方程式$C_n^m\equiv C_{n/p}^{m/p}*C_{n\%p}^{m\%p}(mod~p)$。此即$\text{Lucas}$定理，比之前的所有方法都省时间。

证明如下：
1. 令$m=x_1*p+y_1,n=x_2*p+y_2$，则等式右侧可转化为$C_{x_2}^{x_1}*C_{y_2}^{y_1}$；
2. $C_n^m$是$(x+1)^n$的展开式中$x^m$项的系数，用$x_1*p+y_1$替换$m$，就转化为了$x^{x_1*p}*x^{y_1}$；用$x_2*p+y_2$替换$n$，可以得到$(x+1)^{x_2*p+y_2}$，即$((x+1)^p)^{x_2}*(x+1)^{y_2}$，模$p$的情况下，可以替换成$(x^p+1)^{x_2}*(x+1)^{y_2}$；
3. 由最初的代换可得$y_1=m\%p,y_2=n\%p$，必然小于$p$，而$x^p+1$的幂次展开式中，除了常数项外，包含$x$的幂次必然是$p$的倍数，不可能小于$p$，因此$x^{y_1}$项必然由$(x+1)^{y_2}$提供，$x^{x_1*p}$项必然由$(x^p+1)^{x_2}$提供；
4. $x^{x_1*p}$项的系数为$C_{x_2}^{x_1}$，$x^{y_1}$项的系数为$C_{y_2}^{y_1}$，相乘即为$C_{x_2}^{x_1}*C_{y_2}^{y_1}$，它等同于$C_n^m$；
5. $C_n^m\equiv C_{n/p}^{m/p}*C_{n\%p}^{m\%p}(mod~p)$得证，则$C_n^m\%p=(\prod_{i=0}^{n}C_{b_i}^{a_i})\%p$也一定是正确的

该部分的函数用$\text{lucas}$命名，以区别于前面的$\text{combine}$，在计算过程中，前面的$\text{combine}$需要重复利用。函数$\text{lucas}$有迭代和递归两种写法，迭代法用到了$C_n^m\%p=(\prod_{i=0}^{n}C_{b_i}^{a_i})\%p$，而递归法用到了$C_n^m\equiv C_{n/p}^{m/p}*C_{n\%p}^{m\%p}(mod~p)$

迭代：

size_t lucas(size_t n, size_t m, size_t p) {
    size_t ans = 1;
    while (n > 0 && m > 0) {                //取到0那就是1
        size_t a = m % p, b = n % p;        //依次取一位
        m /= p;
        n /= p;
        ans = (ans * combine(b, a, p)) % p; //按累乘式计算
    }
    return ans;
}

递归：

size_t lucas(size_t n, size_t m, size_t p) {
    if (m == 0) return 1;
    //取模部分的组合数用combine算出来，除法部分的组合数继续递归调用lucas
    return lucas(n / p, m / p, p) * combine(n % p, m % p, p);
}