hdu 1133(卡特兰数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1133

卡特兰数的应用：( C(m+n, n) - C(m+n, m+1) ) * m! * n! 化简即 (m+n)! * (m-n+1) / (m+1)

string处理比较方便。。。

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<vector>
 5 using namespace std;
 6 vector<string>vet;
 7 
 8 string Mul(string &str,int n){
 9     string s="";
10     int len=str.size();
11     int c=0,l=0;
12     for(int i=len-1;i>=0;i--){
13         c=l+(str[i]-'0')*n;
14         l=c/10;
15         s+=c%10+'0';
16     }
17     while(l){
18         s+=l%10+'0';
19         l=l/10;
20     }
21     reverse(s.begin(),s.end());
22     return s;
23 }
24 
25 void Facs(){
26     vet.push_back("0");
27     vet.push_back("1");
28     vet.push_back("2");
29     string str="2";
30     for(int i=3;i<=204;i++){
31         str=Mul(str,i);
32         vet.push_back(str);
33     }
34 }
35 
36 string Divide(string &str,int n){
37     string s="";
38     int len=str.size();
39     int c=0,l=0;
40     for(int i=0;i<=len-1;i++){
41         c=l*10+str[i]-'0';
42         l=c%n;
43         c=c/n;
44         if(c==0&&s.size()==0)continue;
45         else s+=c+'0';
46     }
47     return s;
48 }
49 
50 int main(){
51     Facs();
52     int n,m;
53     int _case=1;
54     while(~scanf("%d%d",&m,&n)){
55         if(n==0&&m==0)break;
56         printf("Test #%d:\n",_case++);
57         if(m<n){
58             printf("0\n");
59             continue;
60         }
61         string str=vet[n+m];
62         str=Mul(str,m-n+1);
63         str=Divide(str,m+1);
64         cout<<str<<endl;
65     }
66     return 0;
67 }