[模板] 常用数学-阶乘逆元排列组合

lli fac[maxn];  // 阶乘
lli inv[maxn];  // 逆元
lli invf[maxn]; // 逆元的阶乘

inline void init() { 
    fac[0] = 1;
    for (lli i = 1; i < maxn; ++i)
        fac[i] = fac[i - 1] * i % mod;
    inv[1] = 1;
    for (lli i = 2; i < maxn; ++i)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    invf[0] = 1;
    for (lli i = 1; i < maxn; ++i)
        invf[i] = invf[i - 1] * inv[i] % mod;
}

inline lli finv(lli x) { return x < maxn ? inv[x] : finv(mod % x) * (mod - mod / x) % mod; }
inline lli c(lli n, lli m) { return fac[n] * invf[m] % mod * invf[n - m] % mod; }
inline lli a(lli n, lli m) { return c(n, m) * fac[m] % mod; }

发表评论