低级版

方法概述

直接用组合数性质中的③式递推即可

程序实现

int mod,c[2010][2010];
int C(int n)
{
    for(int i=0;i<=n;i++) c[i][0]=1;
    c[1][1]=1;
    for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

时间复杂度

$\Theta (n^2)$

高级版

方法概述

这一种求组合数的方法用到了一个著名的定理——Lucas定理！
我们先来了解一下这个神奇的定理

Lucas定理

设$p$为质数，$\binom{n}{m}\equiv\binom{n/p}{m/p}\binom{n\%p}{m\%p}\pmod{p}$
证明：设$n=sp+q,m=tp+r$且$q,r<p$
$\because (1+x)^p\equiv (1+x^p)\pmod{p}$（费马小定理）
$\therefore (1+x)^n\equiv (1+x)^{ps}(1+x)^q\equiv\left(1+x^p\right)^s(1+x)^q=\sum \limits_{i=0}^s\binom{s}{i}x^{ip}\times \sum \limits_{j=0}^{q}\binom{q}{j}x^j=\sum \limits_{i=0}^{sp+q}\binom{sp+q}{i}x^i\pmod{p}$
$\therefore \binom{s}{t}\binom{q}{r}\equiv\binom{sp+q}{tp+r}\equiv \binom{n}{m}\pmod{p}$（$x^{tp+r}$的系数）
$\therefore \binom{n}{m}\equiv\binom{n/p}{m/p}\binom{n\%p}{m\%p}\pmod{p}$
有了这个定理，我们就可以用来解决$p$为质数的情况了，只需要递归一下就可以了
但是$p$不是质数呢？~~那肯定是出题人看你不爽，故意搞你~~
这时候，我们就要请出我们的救星——exLucas定理！

exLucas定理

其他

分段打表万岁！