【题目来源】
【题目描述】
给定整数 n，m，p 的值，求出 C(n+m, n) mod p 的值。
输入数据保证 p 为质数。
注：C 表示组合数。
【输入格式】
本题有多组数据。
第一行一个整数 T，表示数据组数。
对于每组数据：一行，三个整数 n，m，p。
【输出格式】
对于每组数据，输出一行，一个整数，表示所求的值。
【输入样例】
2
1 2 5
2 1 5
【输出样例】
3
3
【数据范围】
对于 100% 的数据，1≤n,m,p≤10^5，1≤T≤10。
【算法分析】
● Lucas 定理是数论中用于计算组合数 C(n, m) 模素数 p 的值的经典定理，由法国数学家 Édouard Lucas 提出。其核心思想是将大数的组合数模运算分解为更小规模的子问题，适用于模数为素数的应用场景。
● 算法竞赛中，常用 Lucas 定理的如下形式。
C(n, m) ≡ C(n%p, m%p) • C(n/p, m/p) (mod p)，其中 p 为素数。
● Lucas 定理的 C++ 代码如下所示。
typedef long long LL;LL C(LL n,LL m,LL p) {if(m>n) return 0;return fac[n]*fastPow(fac[m],p-2,p)*fastPow(fac[n-m],p-2,p)%p;
}LL Lucas(LL n,LL m,LL p) {if(m==0) return 1;else return C(n%p,m%p,p)*(Lucas(n/p,m/p,p))%p;
}
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1e5+5;
LL fac[N];
int T;int fastPow(LL a,LL n,LL p) {LL ans=1;while(n) {if(n & 1) ans=ans*a%p;n>>=1;a=a*a%p;}return ans%p;
}LL C(LL n,LL m,LL p) {if(m>n) return 0;return fac[n]*fastPow(fac[m],p-2,p)*fastPow(fac[n-m],p-2,p)%p;
}LL Lucas(LL n,LL m,LL p) {if(m==0) return 1;else return C(n%p,m%p,p)*(Lucas(n/p,m/p,p))%p;
}int main() {fac[0]=1;cin>>T;while(T--) {LL n,m,p;cin>>n>>m>>p;for(LL i=1; i<=p; i++) {fac[i]=(fac[i-1]*i)%p;}cout<<Lucas(n+m,m,p)%p<<endl;}return 0;
}/*
in:
2
1 2 5
2 1 5out:
3
3
*/
【参考文献】