组合数

题目：http://acm.hrbeu.edu.cn/index.php?act=problem&id=1010&cid=25

题目不难，但是当 a b c都很大时，就不知道怎么算了，当作一个求 c (n, m) % p的模板用吧。

参考链接：http://www.cnblogs.com/gxceo/archive/2011/04/04/2005137.html

因为任何一个实数都可以写成素数的乘积的形式，所以 c (n , m) = n ! / ( m! * (n - m) !) 就可以把这几个数都写成数素的乘积，然后分子分母低数相同的素数的指数进行相减，然后，剩余的数对 c 取余即可，例如样例 2 . c ( 4 , 2) = （2 ^ 3 * 3 ^ 1 ) / ( 2 ^ 1 * 2 ^ 1) 分子的指数分别为：3 1，分母的指数分别为：2，0,所以指数相减后剩余的数是：2 ^ 1 * 3 ^ 1 然后对 c 取余

主要是知道对 n!各个以素数为低进行求指数方法

View Code

 1 const int N = 100000;
 2 const int M = 9592;
 3 int prim[M];
 4 bool vis[N];
 5 int tsum[M],suma[M],sumb[M];
 6 int num,ans;
 7 void is_prime()  // 素数打表
 8 {
 9     int i,j;
10     num = 0;
11     for(i = 2; i <= N; i++)
12     {
13         if(!vis[i]) prim[num ++] = i;
14         for(j = 2; j * i <= N; j++)
15         {
16             if(vis[i * j]) continue;
17             vis[i * j] = true;
18         }
19     }
20 }
21 void solve(int n,int r[])  // 列几个数，看一下以素数为低的指数，找一下规律，就知道这个求法了
22 {
23     int i,j;
24     //_clr(r,0x00);
25     //for(i = 0; i < M; i++)
26     //r[i] = 0;
27     //memset(r,0x00,sizeof(r));
28     memset(r,0x00, M * sizeof(int));  // 这句赋值很神，只要一换成上面那三种赋值就TLE，只有用这个才过
29     for(i = 0; i < M; i++)
30     {
31         if(prim[i] > n) break;  // 这里的一个优化，当素数本身比n大时，就不用再计算指数了
32         for(j = n; j;)
33         {
34             j /= prim[i];
35             r[i] += j;
36         }
37     }
38 }
39 int main()
40 {
41     int i,k;
42     int t,a,b,c;
43     is_prime();
44     //freopen("data.txt","r",stdin);
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%d%d%d",&a,&b,&c);
49         solve(a + b,tsum);
50         solve(a,suma);
51         solve(b,sumb);
52         ans = 1;
53         for(i = 0; i < M; i++)
54         {
55             k = tsum[i] - sumb[i] - suma[i];  // 指数相减
56             while(k--) ans = ans * prim[i] % c;
57         }
58         printf("%d\n",ans);
59     }
60     return 0;
61 }