绪论
对于大组合数对小质数求余的快速算法。
公式
假设 (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_{nmod p}^{mmod p} imes 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 0pmod{p}) 。
然后，我们构造关于 (n) 的组合数的生成函数：
[(1+x)^n=(1+x)^{kp+r}=((1+x)^p)^k imes (1+x)^requiv(1+x^p)^k imes (1+x)^rpmod{p}
]
显然，乘积中第 (m) 项的系数，要么是 (0) ，要么是 (C_r^{mmod p} imes C_k^{[frac{m}{p}]}) 。于是证明了其表达形式的第二种。