快速幂
作用:在\(O(\log_2 n)\)的时间里快速计算\(k^n\bmod p)的值
将指数写成二进制的形式,你会发现乘方运算变成了这个形式:
$$k^n=\prod_{n\&2^{i-1}=1} k^{2^i}$$
然后我们就可以将i从1到32试一遍啦
template<typename IntType> IntType qpow(IntType base, IntType exp, IntType mod) { IntType ans = 1; while (exp != 0) { if (exp % 2 == 1) ans = ans * base%mod; base = base * base%mod; exp /= 2; } return ans; }
乘法逆元
有时我们要计算\(\bmod p\)意义下的除法,即计算 \(\frac{a}{b}\pmod p\)
相当于找一个\(c\)使得 \(bc\equiv 1\pmod p\)
按照费马小定理,当\(p\)为质数时,有 \(a^{p-1}\equiv 1\pmod p\)
即\(a\)的逆元为\(a^{p-2}\bmod p\)
直接用快速幂计算就可以啦
a*qpow(a, p-2, p) % p;
乘法逆元的线性递推公式
我们现在要求\(k\)的逆元,设\(i=\lfloor\frac{p}{k}\rfloor,j=p\bmod k\),有\(p=ki+j\),则有:
$$ki+j\equiv 0\pmod p$$
$$ki\equiv -j \pmod p$$
$$k\equiv -i^{-1}j \pmod p$$
$$1\equiv -i^{-1}k^{-1}j \pmod p$$
$$k^{-1}\equiv -ij^{-1} \pmod p$$
然后就推出来了
inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = (p - p/i) * inv[p%i] % p;
卢卡斯定理
当\(p\)为质数时有:
$$C^m_n=C^{\lfloor\frac{m}{p}\rfloor}_{\lfloor\frac{n}{p}\rfloor}\times C^{m\bmod p}_{n\bmod p}$$
当\(n, m\)均比较小时可以直接按照公式计算:
$$C^m_n=\frac{n!}{m!(n-m)!}$$
int qpow(int base, int exp, int mod) { int ans = 1; while (exp != 0) { if (exp % 2 == 1) ans = ans * base%mod; base = base * base%mod; exp /= 2; } return ans; } int fact[8000001]; void prepfact(int cnt, int mod) { fact[0] = 1; for (int i = 1; i <= cnt; i++) fact[i] = fact[i - 1] * i % mod; } // C_n^m = frac{n!}{m!\left(n-m\right)!} int smallc(int n, int m, int mod) { if (n == 0 || m == 0) return 0; if (n < m) return 0; return fact[n] * qpow(fact[m], mod - 2, mod) % mod*qpow(fact[n - m], mod - 2, mod) % mod; } int c(int n, int m, int mod) { int ans = 1; while (n != 0 && m != 0 && ans != 0) { ans = ans * smallc(n%mod, m%mod, mod) % mod; n /= mod; m /= mod; } return ans; }