组合数学基础

此页面存在相关页面。关于反演与组合恒等式，请参见「组合数学再基础」。

排列组合 + 二项式定理 + 卢卡斯（lucas）定理……

一 排列组合

1 概念

从$n$个不同元素中取$m(m\leqslant n)$个形成一个排列，所得到的排列的总数被称作排列数，记作$A_n^m$。
从$n$个不同元素中取$m(m\leqslant n)$个形成一个集合，所得到的集合的个数被称作组合数，记作$C_n^m$。

2 公式

通项公式
$$ A_n^m = \dfrac{n!}{(n-m)!} $$
$$ C_n^m = \dfrac{n!}{m!(n-m)!} $$

推导式
$$C_n^m = \dfrac{A_n^m}{m!}$$

递推式
$$ C_n^m = C_{n-1}^m+C_{n-1}^{m-1} $$

对称性
$$ C_n^m = C_n^{n-m} $$
组合数具有对称性。假设你现在有一张$C_1^1\text{~} C_n^m$的组合数表，那么这张表的第$i$横行应该是以$i/2$为轴呈左右对称的。

---

二 二项式定理

其实组合数、杨辉三角、二项式定理都可以看成一个东西……

二项式定理用于求$(x+y)^n$的展开式。
定理的内容如下（公式表示）：
$$ (x+y)^n = \sum\limits_{k=0}^n C_n^kx^ky^{n-k} $$

有一个比较有意思的地方：当$p$是素数时，$ (x+y)^p \equiv x^p+y^p (\text{mod }p)$。

因为$ \sum\limits_{k=0}^p C_p^kx^ky^{p-k} $可以拆成$x^p+y^p + \sum\limits_{k=1}^{p-1} C_p^kx^ky^{p-k}$，后面的$\sum\limits_{k=1}^{p-1} C_p^kx^ky^{p-k}$中，每一项都有一个$C_p^k(k\in [1,p-1] )$。用通项公式，那么$C_p^k$可以变成$\dfrac{p!}{k!(p-k)!}$，分子部分的$p!$含有$p$这一项，故$p!\equiv 0 (\text{mod }p)$；同时$p$这一项不会被约分掉（因为$p$是质数），故$\dfrac{p!}{k!(p-k)!}\equiv 0 (\text{mod }p)$，故$C_p^k\equiv 0 (\text{mod }p,k\in [1,p-1])$，故$\sum\limits_{k=1}^{p-1} C_p^kx^ky^{p-k}\equiv 0 (\text{mod }p)$，故得证。

---

三 卢卡斯定理

1 理论

卢卡斯（lucas）定理用来求$ C_n^m \text{ mod } p$的值，其中$p$为素数。
题外话：当$p$不是素数的时候要用扩展卢卡斯（ex-lucas），貌似还要用CRT，真是吓死我了……

定理的内容：$$ C_n^m \text{ mod } p = (C_{n \text{ mod } p}^{m \text{ mod } p}\times C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}) \text{ mod } p $$

根据乘法取余的运算原则，可以拆出$C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor} \text{ mod } p$这一项。这个可以继续用lucas递归求。

剩下部分是$C_{n \text{ mod } p}^{m \text{ mod } p}\text{ mod } p$，可知$n,m$都不会超过或等于$p$，那么尝试暴力求。

当$p$一定时，显然可以打一个阶乘取余的表，不再多说。如果不打表，用通项公式求的极限复杂度大约是$O(p)$（忽略了常数），实际上可以再优化一下常数。
当组合数有意义（即$m\leqslant n$）时，$n!$中实际上包含了$m!$。于是通项公式可以变形为：$$C_{n}^{m} \text{ mod } p = \dfrac{n(n-1)(n-2)…(m+1)}{(n-m)!} \text{ mod } p $$这个式子涉及到除法的取余，所以需要引入$(n-m)!$在模$p$意义下的逆元$\text{inv}[(n-m)!]$。$p$是个质数，用费马小定理就好了。最终变形为：
$$C_{n}^{m} \text{ mod } p =n(n-1)(n-2)…(m+1)·\text{inv}[(n-m)!] \text{ mod } p $$

然后根据组合数的对称性，$ C_n^m = C_n^{n-m} $，那么我们在$m,n-m$挑一个小的代入式子求组合数就好了。极限复杂度大概是严格的$O(p)$。

考虑到多组数据的话，该算法适用数据范围大约是$p\leqslant 10^5$。

2 代码

模板

#define LL long long

LL QuickPow(LL a,LL b,LL r){ //快速幂取余
    LL base = a%r,rec = 1;
    while(b){
        if(b & 1) (rec *= base) %= r;
        (base *= base) %= r;
        b >>= 1;
    }
    return rec % r;
}
int C(int n,int m,int p){ //计算组合数
    if(m > n) return 0;
    if(m > n-m) m = n-m; //这里用到对称性 
    
    LL s1 = 1,s2 = 1;
    for(int k=m+1;k<=n;k++)
        (s1 *= k) %= p;
    for(int k=2;k<=n-m;k++)
        (s2 *= k) %= p;
    LL inv = QuickPow(s2,p-2,p); //求逆元 
    
    return (s1*inv) % p;
}
int lucas(int n,int m,int p){ //主求解函数，返回C(n,m) mod p的值
    if(!m) return 1; //边界
    return (C(n%p,m%p,p)*lucas(n/p,m/p,p)) % p;
}

时间复杂度大概是$O(t·p\log_pn)$，$t$是数据组数。