对于大组合数对小质数求余的快速算法。
假设 \(n=\prod_{i=0}^k{a_ip^i},m=\prod_{i=0}^k{b_ip^i}\) ，其中 \(p \in \mathbb{P}\) （就是说，是质数），那么有：
\[C_n^m=\prod_{i=0}^k{C_{a_i}^{b_i}}\]
容易发现，可以表示成：
\[C_n^m=C_{n\mod p}^{m\mod p}\times C_{[\frac{n}{p}]}^{[\frac{m}{p}]}\]
这就是一个容易编码的递归形式。
定义两个多项式同余，为两个多项式的每一次项的系数在模意义下相等。
然后显然，我们有 \(C_n^i=\frac{n!}{i!(n-i)!}=\frac{n}{i}\frac{(n-1)!}{(i-1)!(n-i)!}=\frac{n}{i}C_{n-1}^{i-1}\equiv 0\pmod{p}\) 。
然后，我们构造关于 \(n\) 的组合数的生成函数：
\[(1+x)^n=(1+x)^{kp+r}=((1+x)^p)^k\times (1+x)^r\equiv(1+x^p)^k\times (1+x)^r\pmod{p}\]
显然，乘积中第 \(m\) 项的系数，要么是 \(0\) ，要么是 \(C_r^{m\mod p}\times C_k^{[\frac{m}{p}]}\) 。于是证明了其表达形式的第二种。
原文：https://www.cnblogs.com/pupuvovovovo/p/11704967.html