【题目来源】
AcWing：887. 求组合数 III - AcWing题库
【题目描述】
给定 \(n\) 组询问，每组询问给定三个整数 \(a,b,p\)，其中 \(p\) 是质数，请你输出 \(C_a^b\ mod\ p\) 的值。
【输入】
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一组 \(a,b,p\)。
【输出】
共 \(n\) 行，每行输出一个询问的解。
【输入样例】
3
5 3 7
3 1 5
6 4 13
【输出样例】
3
3
2
【算法标签】
《AcWing 887 求组合数III》 #组合数学# #组合计数# #Lucas定理# #逆元# #快速幂# #费马小定理#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用long long类型防止溢出
int p; // 模数，必须是质数// 快速幂算法，计算 a^b mod p
int qmi(int a, int b)
{int mul = 1; // 结果初始化为1while (b) // 当指数b不为0时继续{if (b & 1) // 如果b的最低位是1{mul = mul * a % p; // 将当前a乘入结果}a = a * a % p; // a自乘b >>= 1; // b右移一位}return mul; // 返回a^b mod p
}// 直接计算组合数 C(a, b) mod p，要求 a,b < p
int C(int a, int b)
{if (b > a) return 0; // 如果b>a，组合数为0if (b > a - b) b = a - b; // 使用对称性 C(a,b)=C(a,a-b)，减少计算量int res = 1; // 结果初始化为1// 计算 C(a, b) = a! / (b! * (a-b)!) = a*(a-1)*...*(a-b+1) / b!for (int i = 1, j = a; i <= b; i++, j--){// 分子：j = a, a-1, ..., a-b+1res = res * j % p;// 除以分母的第i项i// 费马小定理：i^{-1} ≡ i^{p-2} (mod p)res = res * qmi(i, p - 2) % p;}return res; // 返回 C(a, b) mod p
}// 卢卡斯定理递归计算组合数
int lucas(int a, int b)
{if (b == 0) return 1; // 基本情况：C(a, 0) = 1// 如果a,b都小于p，直接计算if (a < p && b < p){return C(a, b);}// 卢卡斯定理：C(a, b) ≡ C(a mod p, b mod p) * C(a/p, b/p) (mod p)return C(a % p, b % p) * lucas(a / p, b / p) % p;
}signed main() // 因为使用了#define int long long，所以用signed main
{int n; // 查询次数cin >> n;while (n--) // 处理每个查询{int a, b; // 输入C(a, b)cin >> a >> b >> p; // 输入a, b和模数p// 使用卢卡斯定理计算组合数cout << lucas(a, b) << endl;}return 0;
}
【运行结果】
3
5 3 7
3
3 1 5
3
6 4 13
2