原题链接
代码 1:用快速幂(模数为质数)求逆元
// 核心:预处理出阶乘
#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7, N = 1e5 + 7;
LL fact[N], infact[N];
LL fastpow(int a, int k, int p) {
LL res = 1;
while (k) {
if (k & 1) res = res * 1ll * a % p;
a = a * 1ll * a % p;
k >>= 1;
}
return res;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i <= N; i ++) {
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * fastpow(i, mod - 2, mod) % mod;
}
}
int main() {
int n;
cin >> n;
init();
while(n --) {
int a, b;
cin >> a >> b;
LL res = fact[a] * infact[a - b] % mod * infact[b] % mod;
cout << res << endl;
}
return 0;
}
代码 2:用扩展欧几里得算法求逆元
// 核心:预处理出阶乘
#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7, N = 1e5 + 7;
LL fact[N], infact[N];
LL x, y;
LL exgcd(int a, int b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void init() {
fact[0] = infact[0] = 1;
for (int i = 1; i <= N; i ++) {
fact[i] = fact[i - 1] * i % mod;
exgcd(i, mod, x, y);
x = (x % mod + mod) % mod; // 让x取正整数
infact[i] = infact[i - 1] * x % mod;
}
}
int main() {
int n;
cin >> n;
init();
while(n --) {
int a, b;
cin >> a >> b;
LL res = fact[a] * infact[a - b] % mod * infact[b] % mod;
cout << res << endl;
}
return 0;
}