一、高中数学公式复习
\(C_n^m = \frac{n!}{m!(n-m)!}\)
\(C_n^m = C_n^{n-m} = C^{m}_{n-1} + C^{m-1}_{n-1}\)
\(C_n^0+C_n^1+C_n^2+...+C_n^n = \sum_{i=0}^{n}{C_n^i} = 2^n\)
\(C_n^0+C_n^2+C_n^4+... = C_n^1+C_n^3+C_n^5+... = 2^{n-1}\)
\(C_n^m+C_{n+1}^m+C_{n+2}^m+...+C_{n+m}^m = \sum_{i=0}^{m}C_{n+i}^{m} = C_{n+m+1}^{m+1}\)
\(k C_n^k = nC_{n-1}^{k-1}\)， \(\frac{C_n^k}{k+1} = \frac{C_{n+1}^{k+1}}{n+1}\) （好吧这个没学过但是既然看到了就一并抄过来了）
二、快速求组合数取模C(n, m)%p
当n和p大小不同时方法有不同。
1. n很小，p随意，p不需要为素数
1) 原理
使用杨辉三角：\(C^{m}_{n}\%p = (C^{m-1}_{n-1}+C^{m}_{n-1})\%p\)。
组合数C(n, m)其实就是杨辉三角第n行第m列的值（下标从0开始算的话）。每一行的各个值都是迭代上一行的结果。那么用二维数组打个表即可，for里套个for。
2) 我的模板
1 | typedef long long lld; |
2. n相对小（方便打表），p可以很大，p要求为素数
1) 原理
仅使用费马小定理： 若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1， 即a^(p-1) ≡ 1 （mod p），所以a^(p-2) ≡ 1/a (mod p)。所以a的逆元为a^(p-2)。于是将\(\frac{n!}{m!(n-m)!}\) 中的除法全变成了乘法：
得到公式：\(C^{m}_{n}\%p = ((n!)\%p*[(n-m)!]^{p-2}\%p*(m!)^{p-2}\%p)\%p\)
2) 我的模板
1 | lld pow_mod(lld a, lld b, const int &pr) |
可以看到这里最麻烦的是求阶乘fac(n)，如果n不大的话打表是极好的。n较大的话使用以下公式递归求得：
\(n! = \frac{n!}{(\frac{n}{2})!\frac{n}{2})!}*[(\frac{n}{2})!]^2 = C^{n/2}_n*[(\frac{n}{2})!]^2\)
具体以后再写一篇求阶乘。
1 | lld C_small(lld n, lld m, const int &pr) |
这是不打表的版本（其实就是没打表而已，没什么区别）。
3. n很大时要求p较小（p<10^5），p要求为素数
1) 原理
使用Lucas定理：\(C^{m}_{n}\%p =(C^{m\%p}_{n\%p}C^{m/p}_{n/p})\%p\)。
为什么要求p挺小，由公式就可以看出，p太大了的话\(C^{m\%p}_{n\%p}\)也依然很大。Lucas定理用到了费马小定理，要求p为素数。对于每个\(C^{m/p}_{n/p}\)，递归调用Lucas定理。可以看见n被p取模后很容易就变小了，所以要求p较小。
定理证明：网上看到的大神的博客
2) 我的模板
1 | typedef long long lld; |
C_small就是用求逆元求解，像法二一样做打表也是极好的。 如果n不大，p很大，用一下Lucas定理后也就相当于执行了法二，所以以后直接用Lucas即可。
三、Vandermonde恒等式
范德蒙（Vandermonde）恒等式：
\[C^{k}_{n+m} = \sum^{k}_{i=0}C^{i}_{n}C^{k-i}_{m}\]
其中k肯定得小于等于min(n,m)。
理解：从n个黑球、m个白球里找k个球有多少方式。
当\(k=min(n,m)\)时，这里假设\(m<n\)，那就是\(k=m\)时，可以变个形：
\[C^{k}_{n+m} = \sum^{k}_{i=0}C^{i}_{n}C^{m-k+i}_{m} = \sum^{m}_{i=0}C^{i}_{n}C^{i}_{m}\]
那意义就是n个黑球和m白个球中各找0个、1个、2个……m个对应颜色的球，一共有多少方法。