首页 > 代码库 > 【模版】卢卡斯定理
【模版】卢卡斯定理
给定n,m,p
求 (m改为n)
C表示组合数。
一个测试点内包含多组数据。
输入输出格式
输入格式:
第一行一个整数T,表示数据组数
第二行开始共T行,每行三个数n m p,意义如上
输出格式:
共T行,每行一个整数表示答案。
输入输出样例
输入样例#1:
2 1 2 5 2 1 5
输出样例#1:
3 3
Lucas定理是用于处理组合数取模的定理
通常用于解决阶乘无法解决的问题。
cm(a,b)=a!*(b!*(a-b)!)^(p-2)mod p
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 long long p,a[1000001]; 7 long long qpow(int x,int m) 8 { 9 if (m==0) return 1; 10 long long tmp=qpow(x,m/2); 11 tmp=(tmp*tmp)%p; 12 if (m%2==1) tmp=(tmp*x)%p; 13 return tmp; 14 } 15 long long getc(int n,int m) 16 { 17 if (n<m) return 0; 18 if (m>n-m) m=n-m; 19 return (a[n]*qpow(a[m],p-2))%p*qpow(a[n-m],p-2)%p; 20 } 21 long long lucas(int n,int m) 22 { 23 if (m==0) return 1; 24 return (getc(n%p,m%p)*lucas(n/p,m/p)%p); 25 } 26 int main() 27 {int n,m,T; 28 int l,i; 29 cin>>T; 30 for (l=1;l<=T;l++) 31 { 32 scanf("%d%d%d",&n,&m,&p); 33 a[0]=1; 34 for (i=1;i<=p;i++) 35 a[i]=(a[i-1]*i)%p; 36 printf("%lld\n",lucas(n+m,n)); 37 } 38 }
【模版】卢卡斯定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。