首页 > 代码库 > BZOJ2982: combination

BZOJ2982: combination

2024-07-24 20:15:13   215人阅读

2982: combination

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 124  Solved: 68
[Submit][Status]

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

Sample Output

5
10
35
6

HINT

Source

题解：

无节操的题目背景。。。

就是求C（n，m） mod 10007

果然是lucas定理裸题

lucas定理：若p为素数，则 c（n，m） mod p=c（n%p，m%p）*c（n/p，m/p）mod p

左边的部分直接暴力+逆元+快速幂解决，右边的部分递归下去即可。注意边界情况的处理

代码：

  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 500+100 26  27 #define maxm 500+100 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 10007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 int n,m,cs; 61 int power(int x,int y) 62 { 63     int t=1; 64     for(;y;y>>=1,x*=x,x%=mod) 65         if(y&1)t*=x,t%=mod; 66     return t; 67 } 68 int getc(int n,int m) 69 { 70     if(n<m)return 0; 71     m=max(m,n-m); 72     int t1=1,t2=1; 73     for2(i,m+1,n)t1*=i,t1%=mod; 74     for2(i,2,n-m)t2*=i,t2%=mod; 75     return (t1*power(t2,mod-2))%mod; 76 } 77      78 inline int lucas(int n,int m) 79 { 80     return m?(getc(n%mod,m%mod)*lucas(n/mod,m/mod))%mod:1; 81 } 82  83 int main() 84  85 { 86  87     freopen("input.txt","r",stdin); 88  89     freopen("output.txt","w",stdout); 90  91     cs=read(); 92     while(cs--) 93     { 94         n=read();m=read(); 95         printf("%d\n",lucas(n,m)); 96     } 97  98     return 0; 99 100 }
View Code

 

BZOJ2982: combination


联系
我们