求逆元和组合数模板

求逆元

$O(n)$求逆元

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

$O(n)$求阶乘

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

求$n\choose k$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$

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