根据公式c = a! / [b! * (a - b)!],直接算是很简单的,但因为有除法会超时,关键在于用逆元将乘法转换为除法
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
fact[0] = infact[0] = 1; //fact阶乘,infact阶乘的逆元
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
int n;
cin >> n;
while (n -- )
{
int a, b;
cin >> a >> b;
//由公式c = a! / [b! (a - b)!]
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}
我觉得其实是因为 $ \frac{a}{b}\%mod \ne \frac{a\%mod}{b\%mod}\%mod $ 吧?