如何高效计算组合数C(n, m)？
摘要：72.Acwing基础课第886题-简单-求组合数Ⅱ 题目描述 (给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C^b_amod(10^9+7)的值)。 输入格式 (第一行包含整数 n)。 (接下来
72.Acwing基础课第886题-简单-求组合数Ⅱ
题目描述
\(给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C^b_amod(10^9+7)的值\)。
输入格式
\(第一行包含整数 n\)。
\(接下来 n 行，每行包含一组 a 和 b\)。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
\(1≤n≤10000\)，
\(1≤b≤a≤10^5\)
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
代码：
// 包含基础输入输出、算法头文件
#include <iostream>
#include <algorithm>
using namespace std;
// 定义长整型别名：防止乘法过程中溢出int范围（如1e5!的中间结果极大）
typedef long long LL;
// 常量定义：
// N=100010：预处理阶乘/逆元的最大范围（支持C(a,b)中a≤1e5）
// mod=1e9+7：模数（质数，适配费马小定理求逆元）
const int N = 100010, mod = 1e9 + 7;
// 预处理数组：
// fact[i] = i! mod mod（i的阶乘模mod）
// infact[i] = (i!)^{-1} mod mod（i!的乘法逆元模mod）
int fact[N], infact[N];
// 快速幂函数：计算 (a^k) mod p 的结果（费马小定理求逆元的核心）
// 参数：a-底数，k-指数，p-模数（本题中p=mod是质数）
int qmi(int a, int k, int p)
{
int res = 1; // 初始化结果为1（乘法单位元）
// 二进制分解指数k，时间复杂度O(logk)
while (k)
{
// k&1：判断k的二进制最低位是否为1（等价于k%2==1）
if (k & 1) res = (LL)res * a % p; // 结果乘当前底数，转LL防溢出
a = (LL)a * a % p; // 底数平方，转LL防溢出
k >>= 1; // 指数右移一位（等价于k /= 2）
}
return res; // 返回 (a^k) mod p
}
int main()
{
// ========== 预处理阶乘和阶乘的逆元 ==========
// 边界条件：0! = 1，0!的逆元也为1
fact[0] = infact[0] = 1;
// 遍历1到N-1，预处理每个数的阶乘和阶乘逆元
for (int i = 1; i < N; i ++ )
{
// 阶乘递推：i! = (i-1)! * i mod mod
fact[i] = (LL)fact[i - 1] * i % mod;
// 阶乘逆元递推：(i!)^{-1} = (i-1)!^{-1} * i^{-1} mod mod
// 其中i^{-1}（i的逆元）由费马小定理得：i^(mod-2) mod mod（mod是质数）
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
// ========== 处理多组查询 ==========
int n; // n：查询的组数
scanf("%d", &n);
while (n -- )
{
int a, b; // a：总数；b：选取数（查询C(a,b)）
scanf("%d%d", &a, &b);
// 组合数公式：C(a,b) = a!/(b!*(a-b)!) mod mod
// 模运算中除法等价于乘逆元：C(a,b) = (a! * (b!)^{-1} * (a-b)!^{-1}) mod mod
// 分步取模：避免中间结果溢出，保证每一步都在mod范围内
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}