一些数学知识

快速幂

作用：在\(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;
}