求组合数的五种方法
method1：
(n!/(m!*(n-m)!)) % mod = x %mod ,先对算出n！、m！、(n-m)!对mod取模的余数，就转换为a/b = x%mod;因为m为素数，所以等价于b*x +mod*y = gcd(b,mod); 然后用扩展的欧几里得定理算出 b*x0 +mod*y0 = 1的特解x0，x再进而确定 =(mod + x0%mod) %mod; 则a/b = a*x%mod;
LL e_gcd(LL a, LL b, LL &x, LL &y){ if(b == 0){ x = 1; y = 0; return a; } LL ans = e_gcd(b, a%b, y, x); y -= x*(a/b); return ans; } LL clac(LL a, LL m){ LL x, y; e_gcd(a, m, x, y); return (m + x%m)%m; } LL C(int n, int m){ return fact[n]*clac(fact[m]*fact[n-m]%mod, mod)%mod; }
method2：如果mod是素数 则b的逆元其实就是b^(mod-2)即 (m!*(n-m)!)的逆元为 (m!*(n-m)!)^(mod-2);
LL quickM(LL a, LL b){ LL base = a%mod, ans = 1; while(b){ if(b&1) ans = ans*base%mod; base = base*base%mod; b >>= 1; } return ans; } LL C(int n, int m){ return fact[n]*quickM(fact[m]*fact[n-m]%mod, mod-2)%mod; }
method3：当n和m比较大而mod为素数且比较小(10^5左右)的时候，可以用Lucas定理计算.
Lucas定理:
A、B是非负整数，模数mod = p(p是质数)。A、B写成p进制：
A = a[n]a[n-1]…a[0];
B = b[n]b[n-1]…b[0];
则组合数C(A,B)与C(a[n], b[n])*C(a[n-1], b[n-1])*…*C(a[0], b[0])(mod p)同余
即：Lucas(n, m, p) = c(n%p, m%p)*Lucas(n/p, m/p, p);
hdu 3037：https://www.cnblogs.com/Fy1999/p/9149796.html
LL quickM(LL base, LL b, LL p) { LL ans = 1; while(b) { if(b&1) ans = (ans * base) % p; base = (base*base) % p; b >>= 1; } return ans; } //n,m过大不能打表只能在线求阶乘 LL Comb(LL a, LL b, LL p) { if(a < b) return 0; if(a == b) return 1; if(b > a - b) b = a - b; LL ans = 1, ca = 1, cb = 1; for(LL i = 0; i < b; ++i) { ca = (ca * (a-i)) % p; cb = (cb * (b-i)) % p; } ans = (ca*quickM(cb, p-2, p)) % p; return ans; } LL Lucas(int n, int m, int p) { LL ans = 1; while(n && m && ans) { ans = (ans*Comb(n%p, m%p, p)) % p; n /= p; m /= p; } return ans; }
method4：打表求阶乘数逆元的新方法.
打一个1~n的阶乘的逆元的表，假如n!的逆元叫做f[n]，可以先用费马小定理、扩展欧几里得等
求出f[n]，再用递推公式求出前面的项。
我们记数字 x 的逆元为 f(x) (mod m)。
因为 n! = (n-1)! * n;
所以 f(n!) =
f((n-1)! * n) = f((n-1)!) * f(n);
所以 f((n-1)!) =
f(n!) * f(f(n)) = f(n!) * n; (数的逆元的逆元就是它自身)
这样子我们就可以用后项推出前面的项了。
LL quickM(LL base, LL b) { LL ans = 1; while(b) { if(b&1) ans = (ans * base) % mod; base = (base*base) % mod; b >>= 1; } return ans; } void init() { fact[0] = 1; for(int i = 1; i <= maxn; ++i) fact[i] = fact[i-1]*i%mod; fiv[maxn] = quickM(fact[maxn], mod-2); for(int i = maxn-1; i >= 0; --i) { fiv[i] = fiv[i+1]*(i+1); fiv[i] %= mod; } } LL C(int n, int m) { if(m > n) return 0; return fact[n]*fiv[n-m]%mod*fiv[m]%mod; }
method5：发现一个近乎完美的init(): 阶乘、整数逆元、阶乘逆元，一次O(n)即可。
void init() { fact[0] = fact[1] = 1; fiv[0] = fiv[1] = 1; inv[1] = 1; for(int i = 2; i <= maxn; ++i) { //递推保存fact阶乘，递推求inv和fiv各个逆元 fact[i] = fact[i-1]*i%mod; inv[i] = (mod-mod/i)*inv[mod%i]%mod; fiv[i] = inv[i]*fiv[i-1]%mod; } }
相关链接：
逆元相关知识（大多转自于此）https://blog.csdn.net/yo_bc/article/details/71565988
https://blog.csdn.net/acdreamers/article/details/8220787
卢卡斯定理
https://blog.csdn.net/liangzhaoyang1/article/details/52132986?locationNum=7