首页 > > 程序设计 > C/C++ >

bzoj4807 -- 组合数

2018-06-17 22:55:32来源：未知阅读 ()

容易看出答案就是C(n,m)。。。

然后高精乘一下就可以了。

对n!分解质因数时，质数p的出现次数是n/p+n/p^2+n/p^3+...

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 101
 7 inline int Min(int x,int y){return x<y?x:y;}
 8 inline int Max(int x,int y){return x<y?y:x;} 
 9 struct bign  
10 {  
11     int len, s[MAXN];  
12     bign ()  
13     {  
14         memset(s, 0, sizeof(s));  
15         len = 1;  
16     }  
17     bign (int num) { *this = num; }  
18     bign (const char *num) { *this = num; }  
19     bign operator = (const int num)  
20     {  
21         char s[MAXN];  
22         sprintf(s, "%d", num);  
23         *this = s;  
24         return *this;  
25     }  
26     bign operator = (const char *num)  
27     {  
28         for(int i = 0; num[i] == '0'; num++) ;
29         len = strlen(num);  
30         for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';  
31         return *this;  
32     }
33     void clean()  
34     {
35         if(len>50)len=50;
36         while(len > 1 && !s[len-1]) len--;  
37     }
38     bign operator * (const bign &b)  
39     {  
40         bign c;  
41         c.len = len + b.len;  
42         for(int i = 0; i < len; i++)  
43         {  
44             for(int j = 0; j < b.len; j++)  
45             {  
46                 c.s[i+j] += s[i] * b.s[j];  
47             }  
48         }  
49         for(int i = 0; i < c.len; i++)  
50         {  
51             c.s[i+1] += c.s[i]/10;  
52             c.s[i] %= 10;  
53         }  
54         c.clean();  
55         return c;  
56     }  
57     bign operator *= (const bign &b)  
58     {  
59         *this = *this * b;  
60         return *this;  
61     }  
62 }n;  
63 int i,k,N,M,P[1000010],tot,p[1000010];
64 bool b[1000010];
65 long long j;
66 int main()
67 {
68     scanf("%d%d",&N,&M);
69     if(N<M)swap(N,M);
70     for(i=2;i<=N;i++){
71         if(!b[i])P[++tot]=i;
72         for(j=1;P[j]*i<=N&&j<=tot;j++){
73             b[P[j]*i]=1;
74             if(!(i%P[j]))break;
75         }
76     }
77     for(i=1;i<=tot;i++)
78     for(j=P[i];j<=N;j=j*P[i])p[i]+=N/j;
79     for(i=1;i<=tot;i++)
80     for(j=P[i];j<=M;j=j*P[i])p[i]-=M/j;
81     for(i=1;i<=tot;i++)
82     for(j=P[i];j<=N-M;j=j*P[i])p[i]-=(N-M)/j;
83     n=1;
84     for(i=1;i<=tot;i++)
85     for(j=0;j<p[i];j++)n*=P[i];
86     for(i=n.len-1;i>=0;i--)putchar(n.s[i]+48);
87     return 0;
88 }