(MOD) 是质数,且 (MOD>n) ,可以 (O(n)) 线性预处理阶乘和阶乘逆元, (O(1)) 求组合数 (C_n^m) 。
(MOD) 是质数,且 (MODleq n) ,可以用卢卡斯定理。
(MOD) 不是质数,可以用扩展卢卡斯定理,或者 (C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}) 递推,或者分解阶乘的质因数,用质因数的指数作差避免除法。
线性预处理阶乘和阶乘逆元
const ll MOD = 1e9 + 7;
const int MAXN = 1e6;
ll inv[MAXN + 5], fac[MAXN + 5], invfac[MAXN + 5];
void init_C(int n) {
inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
fac[0] = 1, invfac[0] = 1;
for(int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % MOD;
invfac[i] = invfac[i - 1] * inv[i] % MOD;
}
}
ll C(ll n, ll m) {
if(n < m)
return 0;
return fac[n] * invfac[n - m] % MOD * invfac[m] % MOD;
}
错位排列,D[i]表示i个(不同的)元素全部不在应该在的位置(升序/降序等唯一指定位置)的种类数,可以通过dp求出来,但是还是抄模板方便。
const ll MOD = 1e9 + 7;
const int MAXN = 1e6;
//特殊定义D[0]为1
D[0] = 1, D[1] = 0;
for(int i = 2; i <= MAXN; i++) {
if(i & 1) {
D[i] = ((ll)i * D[i - 1] - 1ll) % MOD;
if(D[i] < 0)
D[i] += MOD;
} else
D[i] = ((ll)i * D[i - 1] + 1ll) % MOD;
}