求逆元与组合数的C++代码

· · 算法·理论

注：由于我是菜鸡，所以可能有的地方会出错。如果发现欢迎告诉我！QWQ

注意如果有减法，需要 (a-b+mod)%mod

排列组合的写法见here

C(n,m) = \frac{n!}{m!(n-m)!}$ 还等于$n!\times(m!)^{-1}\times((n-m)!)^{-1}

可以用到逆元（模数为质数，则 a^{mod-1} = 1，所以 a^{mod-2}=\frac{1}{a}）。

注意ifac是求阶乘的逆元，求单个数的逆元 qpow(a,mod-2);

第一种写法

fac[0] = ifac[0] = 1;
for (int i = 1; i <= maxn; i++) fac[i] = fac[i-1] * i % mod;
for (int i = 1; i <= maxn; i++) ifac[i] = qpow(fac[i], mod - 2) % mod; //qpow是手写的pow，避免精度误差

后面只需要 fac[n] * ifac[n-m] % mod * ifac[m] % mod; 就可以得到 C(n,m)。

第二种写法

省去了一个数组

fac[0] = 1;
for (int i = 1; i <= maxn; i++) fac[i] = fac[i-1] * i % mod;

后面只需要 fac[n] * qpow(fac[n-m] * fac[m] % mod, mod - 2) % mod 就可以得到C(n,m)。

第三种

fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
inv[0] = 1, inv[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % mod;

调用是 fac[n] * inv[m] % mod * inv[n - m] % mod。

线性预处理逆元:（不知道有啥用）

i^{-1} = -\left\lfloor \frac{p}{i} \right\rfloor \cdot (p \bmod i)^{-1} \bmod p 
inv[1] = 1;
for (int i = 2; i < mod; ++i) 
  inv[i] = (mod - mod / i) * inv[mod % i] % mod;
------------ ## 杨辉三角求组合数 众所周知，众所周知。 ```cpp const int tmp = n * m; for (int i = 0; i <= tmp; ++i) c[i][0] = 1; for (int i = 1; i <= tmp; ++i) for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Mod; ``` 调用就不用说了吧？ ------------ 等有时间再分析这些的时间复杂度。 ------------ 快速幂模板：（哦，我是有 `define int long long` 的） ```cpp int qpow(int a, int b) { int ans = 1; while (b > 0) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } ``` ------------ 卢卡斯定理： $C(n,m)=C(n\mod p,m\mod p)\times C(n/p,m/p) (\mod p) 
int Lucas(int n, int m){//Lucas定理求C(n,m)%p 
    if(m == 0) return 1;
    return C(n%p, m%p) * Lucas(n/p, m/p) % p;
}

大佬的卢卡斯定理证明