LL MyPow(LL a, LL b)
{
LL ret = ;
while (b)
{
if (b & )
ret = ret * a % MOD;
a = a * a % MOD;
b >>= ;
}
return ret;
}
LL C(int n, int m)
{
if (m > n || m < ) return ;
LL a = fact[n], b = fact[n - m] * fact[m] % MOD;
return a * MyPow(b, MOD - ) % MOD;//除以一个数，等于乘以这个数的乘法逆元， 然后是在MOD的情况下
}
上面的代码可以计算组合数取模， 能解决的规模大概在10^6左右， 毕竟fact数组再大就开不下了。
那么有lucas定理可以解决n，m很大， 但是p在10^6左右的组合数取模 C(n,m,p) = lucas(n,m,p)
LL pow(LL a, LL k, LL p)
{
LL ret = ;
while (k)
{
if (k & )
ret = ret * a %p;
a = a * a % p;
k >>= ;
}
return ret;
}
LL C(LL n, LL m, LL p)
{
if (n < m || m < ) return ;
LL a = fact[n], b = fact[n - m] * fact[m] % p;
return a * pow(b, p - , p) % p;
}
LL lucas(int n, int m, int p)
{
if (m == ) return ;
return C(n%p, m%p,p) * lucas(n / p, m / p, p) % p;
}
