求逆元和组合数模板

求逆元

$O(n)$求逆元

ll inv[maxn];
inv[1] = 1;
rep(i,2,maxn) 
    inv[i] = inv[mod%i] * (mod-mod/i) % mod;

$O(n)$求阶乘

ll f[maxn];
ll f[1] = 1;
rep(i,2,maxn)
    f[i] = f[i-1]*i;

求$n\choose k$

ll cur,p[maxn],q[maxn],inv[maxn];
ll C(ll n,ll k){
    return p[n]*q[k]%mod*q[n-k]%mod;
}
ll c(ll n,ll k){
    if(n<maxn) return C(n,k);
    if(!k) return 1;
    return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;
}
void init(){
    p[0]=p[1]=q[0]=q[1]=inv[0]=inv[1]=1;
    for(ll i = 2;i<maxn;i++){
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
        q[i] = q[i-1] * inv[i] % mod;
        p[i] = p[i-1] * i % mod;
    }
}
//在每次的时候就得cur初始化为1

求$A^k_n$

int A(int n,int k){
    return c(n,k)*p[k]%mod;
}