sdut2164Binomial Coeffcients（组合数求模）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2164

贴一篇写组合数求mod比较好的帖子

这里的n,m比较小直接利用公式递推求解即可 c(n,m) =c(n - 1,m) + c(n – 1, m – 1)

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<map>
 8 #include<cmath>
 9 #include<stdlib.h>
10 using namespace std;
11 #define LL long long
12 #define mod 10000003
13 int cc[1010][1010];
14 void cn(int n,int m)
15 {
16     int i,j;
17     for(i = 0 ; i <= n ;i++)
18     {
19         cc[i][0] = 1;
20         cc[i][i] = 1;
21         cc[i][1] = i;
22     }
23     for(i = 2; i <= n ; i++)
24         for(j = 1; j <= m ; j++)
25         cc[i][j] = (cc[i-1][j]%mod+cc[i-1][j-1]%mod)%mod;
26 }
27 int main()
28 {
29     int c,n,k,i;
30     cn(1000,1000);
31     cin>>c;
32     while(c--)
33     {
34         cin>>n>>k;
35 
36         printf("%d
",cc[n][k]);
37     }
38     return 0;
39 }
40  
41 
42 
43 
44 /**************************************
45     Problem id    : SDUT OJ 2164 
46     User name    : shang 
47     Result        : Accepted 
48     Take Memory    : 4420K 
49     Take Time    : 10MS 
50     Submit Time    : 2014-01-18 16:32:30  
51 **************************************/

View Code