c(n,m) mod p 1 Lucas 定理

c(n,m) mod p 1 Lucas 定理

（费马小定理，逆元） 看一个例子：​​​Description

给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！

Input

输入数据第一行是一个正整数T,表示数据组数 (T <= 100)接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)

Output

对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。

Sample Input

25 2 35 2 61

Sample Output

110

#include #include using namespace std;typedef long long LL;LL n,m,p;LL power(LL a,LL b){ LL ans=1,temp=a%p; while(b){ if(b&1) ans=ans*temp%p; temp=temp*temp%p; b>>=1; } return ans;}LL cal(LL a,LL b){ // Cm(a,b)=(a!/(a-b)!) * (b!)^(p-2)) mod p if(b>a) return 0; // important LL ans=1; for(int i=1;i<=b;i++){ LL t1=(a-b+i)%p,t2=i%p; ans=ans*(t1*power(t2,p-2)%p)%p; } return ans;}/*Lucas(n,m,p)=Cm(n%p,m%p)* Lucas(n/p,m/p,p)Lucas(x,0,p)=1;*/LL lucas(LL t1,LL t2){ if(t2==0) return 1; return cal(t1%p,t2%p)*lucas(t1/p,t2/p)%p;}int main(){ //freopen("cin.txt","r",stdin); int t; cin>>t; while(t--){ scanf("%lld%lld%lld",&n,&m,&p); printf("%lld\n",lucas(n,m)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。