AcWing 886. 求组合数 II 阶乘逆元倒着求,会快很多,也很好理解
原题链接
简单
作者:
lxm
,
2021-08-22 17:48:34
,
所有人可见
,
阅读 208
时间复杂度$O(n)$
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fac[N], infac[N];
int n;
int qmi(int a, int k, int mod){
int res = 1 % mod;
while (k){
if (k & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
return res;
}
int main(){
fac[0] = infac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = (LL)fac[i - 1] * i % mod;
// 这个显然嘛
infac[N - 1] = qmi(fac[N - 1], mod - 2, mod);
// 这个也显然吧
for (int i = N - 2; i >= 1; i--)
infac[i] = (LL)infac[i + 1] * (i + 1) % mod;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
cout << (LL)fac[a] * infac[a - b] % mod * infac[b] % mod << endl;
}
return 0;
}