Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2923 Accepted Submission(s): 1649
This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.
Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100.
For each n, print in a single line the number of ways to connect the 2n numbers into pairs.
2 3 -1
2 5
Asia 2004, Shanghai (Mainland China), Preliminary
解題思路：
Catalan數，遞推公式為h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1 ，用到了大數模板。
代碼：
#include#include #include #include using namespace std; #define MAXN 9999 #define MAXSIZE 10 #define DLEN 4 class BigNum { private: int a[500]; //可以控制大數的位數 int len; //大數長度 public: BigNum(){ len = 1;memset(a,0,sizeof(a)); } //構造函數 BigNum(const int); //將一個int類型的變量轉化為大數 BigNum(const char*); //將一個字符串類型的變量轉化為大數 BigNum(const BigNum &); //拷貝構造函數 BigNum &operator=(const BigNum &); //重載賦值運算符，大數之間進行賦值運算 friend istream& operator>>(istream&, BigNum&); //重載輸入運算符 friend ostream& operator<<(ostream&, BigNum&); //重載輸出運算符 BigNum operator+(const BigNum &) const; //重載加法運算符，兩個大數之間的相加運算 BigNum operator-(const BigNum &) const; //重載減法運算符，兩個大數之間的相減運算 BigNum operator*(const BigNum &) const; //重載乘法運算符，兩個大數之間的相乘運算 BigNum operator/(const int &) const; //重載除法運算符，大數對一個整數進行相除運算 BigNum operator^(const int &) const; //大數的n次方運算 int operator%(const int &) const; //大數對一個int類型的變量進行取模運算 bool operator>(const BigNum & T)const; //大數和另一個大數的大小比較 bool operator>(const int & t)const; //大數和一個int類型的變量的大小比較 void print(); //輸出大數 }; BigNum::BigNum(const int b) //將一個int類型的變量轉化為大數 { int c,d = b; len = 0; memset(a,0,sizeof(a)); while(d > MAXN) { c = d - (d / (MAXN + 1)) * (MAXN + 1); d = d / (MAXN + 1); a[len++] = c; } a[len++] = d; } BigNum::BigNum(const char*s) //將一個字符串類型的變量轉化為大數 { int t,k,index,l,i; memset(a,0,sizeof(a)); l=strlen(s); len=l/DLEN; if(l%DLEN) len++; index=0; for(i=l-1;i>=0;i-=DLEN) { t=0; k=i-DLEN+1; if(k<0) k=0; for(int j=k;j<=i;j++) t=t*10+s[j]-'0'; a[index++]=t; } } BigNum::BigNum(const BigNum & T) : len(T.len) //拷貝構造函數 { int i; memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++) a[i] = T.a[i]; } BigNum & BigNum::operator=(const BigNum & n) //重載賦值運算符，大數之間進行賦值運算 { int i; len = n.len; memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++) a[i] = n.a[i]; return *this; } istream& operator>>(istream & in, BigNum & b) //重載輸入運算符 { char ch[MAXSIZE*4]; int i = -1; in>>ch; int l=strlen(ch); int count=0,sum=0; for(i=l-1;i>=0;) { sum = 0; int t=1; for(int j=0;j<4&&i>=0;j++,i--,t*=10) { sum+=(ch[i]-'0')*t; } b.a[count]=sum; count++; } b.len =count++; return in; } ostream& operator<<(ostream& out, BigNum& b) //重載輸出運算符 { int i; cout << b.a[b.len - 1]; for(i = b.len - 2 ; i >= 0 ; i--) { cout.width(DLEN); cout.fill('0'); cout << b.a[i]; } return out; } BigNum BigNum::operator+(const BigNum & T) const //兩個大數之間的相加運算 { BigNum t(*this); int i,big; //位數 big = T.len > len ? T.len : len; for(i = 0 ; i < big ; i++) { t.a[i] +=T.a[i]; if(t.a[i] > MAXN) { t.a[i + 1]++; t.a[i] -=MAXN+1; } } if(t.a[big] != 0) t.len = big + 1; else t.len = big; return t; } BigNum BigNum::operator-(const BigNum & T) const //兩個大數之間的相減運算 { int i,j,big; bool flag; BigNum t1,t2; if(*this>T) { t1=*this; t2=T; flag=0; } else { t1=T; t2=*this; flag=1; } big=t1.len; for(i = 0 ; i < big ; i++) { if(t1.a[i] < t2.a[i]) { j = i + 1; while(t1.a[j] == 0) j++; t1.a[j--]--; while(j > i) t1.a[j--] += MAXN; t1.a[i] += MAXN + 1 - t2.a[i]; } else t1.a[i] -= t2.a[i]; } t1.len = big; while(t1.a[len - 1] == 0 && t1.len > 1) { t1.len--; big--; } if(flag) t1.a[big-1]=0-t1.a[big-1]; return t1; } BigNum BigNum::operator*(const BigNum & T) const //兩個大數之間的相乘運算 { BigNum ret; int i,j,up; int temp,temp1; for(i = 0 ; i < len ; i++) { up = 0; for(j = 0 ; j < T.len ; j++) { temp = a[i] * T.a[j] + ret.a[i + j] + up; if(temp > MAXN) { temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); ret.a[i + j] = temp1; } else { up = 0; ret.a[i + j] = temp; } } if(up != 0) ret.a[i + j] = up; } ret.len = i + j; while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; } BigNum BigNum::operator/(const int & b) const //大數對一個整數進行相除運算 { BigNum ret; int i,down = 0; for(i = len - 1 ; i >= 0 ; i--) { ret.a[i] = (a[i] + down * (MAXN + 1)) / b; down = a[i] + down * (MAXN + 1) - ret.a[i] * b; } ret.len = len; while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; } int BigNum::operator %(const int & b) const //大數對一個int類型的變量進行取模運算 { int i,d=0; for (i = len-1; i>=0; i--) { d = ((d * (MAXN+1))% b + a[i])% b; } return d; } BigNum BigNum::operator^(const int & n) const //大數的n次方運算 { BigNum t,ret(1); int i; if(n<0) exit(-1); if(n==0) return 1; if(n==1) return *this; int m=n; while(m>1) { t=*this; for( i=1;i<<1<=m;i<<=1) { t=t*t; } m-=i; ret=ret*t; if(m==1) ret=ret*(*this); } return ret; } bool BigNum::operator>(const BigNum & T) const //大數和另一個大數的大小比較 { int ln; if(len > T.len) return true; else if(len == T.len) { ln = len - 1; while(a[ln] == T.a[ln] && ln >= 0) ln--; if(ln >= 0 && a[ln] > T.a[ln]) return true; else return false; } else return false; } bool BigNum::operator >(const int & t) const //大數和一個int類型的變量的大小比較 { BigNum b(t); return *this>b; } void BigNum::print() //輸出大數 { int i; cout << a[len - 1]; for(i = len - 2 ; i >= 0 ; i--) { cout.width(DLEN); cout.fill('0'); cout << a[i]; } cout << endl; } int main() { BigNum num[102]; num[0]=1; for(int i=1;i<=100;i++) { num[i]=num[i-1]*(4*i-2)/(i+1); } int n; while(cin>>n&&n!=-1) { num[n].print(); } return 0; }
