|
在求组合数时，我们需要用到公式 ( n ) ! ( n − m ) ! ⋅ ( m ) ! \frac{(n)!}{(n-m)!·(m)!} (n−m)!⋅(m)!(n)! ，其中阶乘可以 O n On On的递推预处理，除法取模需要用到逆元，逆元又可以用费马小定理和 e x g c d exgcd exgcd求，不过两者的时间复杂度都是 O l o g n Ologn Ologn，事实上，我们可以先求出最后一个阶乘的逆元，再根据公式 i n v ( n ! ) = i n v ( ( n + 1 ) ! × ( n + 1 ) ) inv(n!)=inv((n+1)!\times (n+1)) inv(n!)=inv((n+1)!×(n+1))线性地倒着推出所有阶乘的逆元。
#define MAXN 1000000
#define mod 1000000007
long long fact[MAXN + 5];
long long inv[MAXN + 5];
long long qpow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
a = (a * a) % p;
b /= 2;
}
return res % p;
}
void init()
{
fact[0] = 1;
for (int i = 1; i = 0; i--)
inv[i] = (inv[i + 1] * (i + 1)) % mod;
}
复制代码
|