组合数求法

方法1：逆元求法

要求MOD是质数 void work() {　　　　 inv[1] = 1; for (int i = 2; i < N; ++i) inv[i] = (MOD - MOD / i)* inv[MOD%i] % MOD;//逆元（原理见下图） f[0] = finv[0] = 1; for (int i = 1; i < N; ++i) { f[i] = f[i-1] * i % MOD;//阶乘 finv[i] = finv[i-1] * inv[i] % MOD;//阶乘的逆元 } }

方法2：杨辉三角

${\text{C}}_n^m$ = ${\text{C}}_n^{n-m}$ = ${\text{C}}_{n-1}^{m-1}$ + ${\text{C}}_{n-1}^m$

只适合n,m都比较小的情况 for (int i = 0; i < N; ++i) { a[i][i] = a[i][0] = 1; for (int j = 1; j < i; ++j) a[i][j] = (a[i-1][j] + a[i-1][j-1])%mod }

方法3：费马小定理

${\text{C}}_n^m$ = $\frac{n!}{m!(n-m)!}$

费马小定理： $b$ ${}^{(p-1)}$ ≡ 1 $(modp)$

ll inv(ll x){ return x==1 ? 1 : (mod-mod/x)*inv(mod%x)%mod;}//求逆元 ll C(ll n,ll m){ if(m < 0 || n < m) return 0;//特判 if(m > n-m) m = n-m;//性质的转换 ll zi = 1, mu = 1;//分子和分母 for(ll i = 0; i < m; i++){ zi = zi * (n-i) % mod;//分子做 n-m+1 ~n 即n!与(n-m)!约掉 mu = mu * (i+1) % mod;//分母做m的阶乘 } return zi * inv(mu) % mod; }

方法4：Lucas定理

可以优化$m,n$都很大的情况，递归解决 ${\text{C}}_n^m$ = ${\text{C}}_{m(mod)p}^{n(mod)p}$ * ${\text{C}}_{m/p}^{n/p}$