线性递推阶乘逆元

在求组合数时，我们需要用到公式$\frac{(n)!}{(n-m)!\cdot (m)!}$ ，其中阶乘可以$On$的递推预处理，除法取模需要用到逆元，逆元又可以用费马小定理和$exgcd$求，不过两者的时间复杂度都是$Ologn$，事实上，我们可以先求出最后一个阶乘的逆元，再根据公式$$inv(n!)=inv((n+1)!)\times (n+1)$$线性地倒着推出所有阶乘的逆元。

#define MAXN 1000000
#define mod 1000000007
long long fact[MAXN + 5];
long long inv[MAXN + 5];

long long qpow(long long a, long long b, long long p)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % p;
        a = (a * a) % p;
        b /= 2;
    }
    return res % p;
}
void init()
{
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++)
        fact[i] = (fact[i - 1] * i) % mod;
    inv[MAXN] = qpow(fact[MAXN], mod - 2, mod);
    for (int i = MAXN - 1; i >= 0; i--)
        inv[i] = (inv[i + 1] * (i + 1)) % mod;
}