31 lines
1.2 KiB
C++
31 lines
1.2 KiB
C++
// https://blog.csdn.net/kiwi_berrys/article/details/54834977
|
||
// https://www.cnblogs.com/zjp-shadow/p/7773566.html
|
||
//阶乘逆元
|
||
#define ll long long
|
||
ll fac[1000000 + 5]; //阶乘
|
||
ll inv[1000000 + 5]; //逆元
|
||
void getfac() {
|
||
fac[0] = inv[0] = 1;
|
||
for (int i = 1; i <= 1000000; i++) {
|
||
fac[i] = fac[i - 1] * i % mod;
|
||
inv[i] = quick_power(fac[i], mod - 2);
|
||
//表示i的阶乘的逆元
|
||
}
|
||
}
|
||
//组合数
|
||
inline ll getC(ll n, ll m) // C(n,m) = n!/((n-m)!*m!) % mod
|
||
{
|
||
return fac[n] * inv[n - m] % mod * inv[m] % mod;
|
||
}
|
||
//当 n，m 过大时，可以用Lucas定理降数据
|
||
inline ll Lucas(ll n, ll m) {
|
||
if (n < mod && m < mod) return getC(n, m);
|
||
return Lucas(n / mod, m / mod) * getC(n % mod, m % mod) % mod;
|
||
}
|
||
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -
|
||
//排列数
|
||
inline ll
|
||
getA(ll n, ll m) // A(n,m) = n!/(n-m)! % mod
|
||
{
|
||
return n * inv[n - m] % mod;
|
||
} |