首页 > 代码库 > 组合数学lucas定理 BZOJ2982 combination
组合数学lucas定理 BZOJ2982 combination
2982: combination
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 597 Solved: 357
[Submit][Status][Discuss]
Description
LMZ有n个不同的基友,他每天晚上要选m个进行[河蟹],而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢?当然,LMZ的一年有10007天,所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
Input
第一行一个整数t,表示有t组数据。(t<=200)
接下来t行每行两个整数n, m,如题意。
Output
T行,每行一个数,为C(n, m) mod 10007的答案。
Sample Input
4
5 1
5 2
7 3
4 2
5 1
5 2
7 3
4 2
Sample Output
5
10
35
6
10
35
6
HINT
Source
此题是lucas定理的裸题
lucas定理的证明改日贴上来
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int mod=10007; 7 int t,n,m; 8 int qpow(int a,int b){ 9 int ans; 10 for(ans=1;b;b>>=1,a=a*a%mod) 11 if(b&1) ans=ans*a%mod; 12 return ans; 13 } 14 int zuhe(int nn,int mm){ 15 if(nn<mm) return 0; 16 if(mm>nn-mm) mm=nn-mm; 17 long long s1=1,s2=1; 18 for(int i=0;i<mm;i++){ 19 s1=s1*(nn-i)%mod; 20 s2=s2*(i+1)%mod; 21 } 22 return s1*qpow(s2,mod-2)%mod;//这里在int范围内 23 } 24 int lucas(int nn,int mm){ 25 if(!mm) return 1; 26 return zuhe(nn%mod,mm%mod)*lucas(nn/mod,mm/mod)%mod; 27 } 28 int main(){ 29 scanf("%d",&t); 30 while(t--){ 31 scanf("%d%d",&n,&m); 32 printf("%d\n",lucas(n,m)); 33 } 34 return 0; 35 }
组合数学lucas定理 BZOJ2982 combination
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。