AcWing 886. 求组合数 II 预处理阶乘 快速幂求逆元
原题链接
简单
作者:
Snrise
,
2024-04-08 20:18:53
,
所有人可见
,
阅读 3
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 100010;
const int MOD = 1e9 + 7;
int fact[N], infact[N];
int n;
int qmi(int a, int n)
{
int res = 1;
while (n)
{
if (n & 1)
{
res = res * a % MOD;
}
a = a * a % MOD;
n >>= 1;
}
return res % MOD;
}
signed main(void)
{
std::ios::sync_with_stdio(false);
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i++)
{
fact[i] = fact[i - 1] % MOD * i % MOD;
infact[i] = infact[i - 1] % MOD * qmi(i, MOD - 2) % MOD;
}
cin >> n;
while (n--)
{
int n, m;
cin >> n >> m;
int res = fact[n] % MOD * infact[m] % MOD * infact[n - m] % MOD;
cout << res << endl;
}
return 0;
}