| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 7136 | Accepted: 3625 |
Description
Input
Output
Sample Input
2 3 -1
Sample Output
2 5
Source
我是巩固一下卡特兰数，顺便存一下高精度模板的。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/3/27 13:57:20
File Name :7.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=9999;
const int maxsize=2020;
const int dlen=4;
class BigNum{
private:
int a[1000],len;
public:
BigNum(){
len=1;memset(a,0,sizeof(a));
}
BigNum(const int b){
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(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(int 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(const BigNum &T):len(T.len){
int i;
memset(a,0,sizeof(a));
for(int i=0;i<len;i++)
a[i]=T.a[i];
}
BigNum operator = (const BigNum &n){
int i;
len=n.len;
memset(a,0,sizeof(a));
for(int i=0;i<len;i++)
a[i]=n.a[i];
return *this;
}
BigNum operator + (const BigNum &T) const{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(int 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])t.len=big+1;
else t.len=big;
return t;
}
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-t1.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 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)ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;
return ret;
}
BigNum operator / (const int &b) const{
BigNum ret;
int i,down=0;
for(int 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;
}
BigNum operator % (const int &b) const{
int i,d=0;
for(int i=len-1;i>=0;i--)
d=((d*(maxn+1))%b+a[i])%b;
return d;
}
BigNum operator ^ (const int &n) const{
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 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 operator > (const int &t) const{
BigNum b(t);
return *this>b;
}
void print(){
int i;
printf("%d",a[len-1]);
for(int i=len-2;i>=0;i--)printf("%04d",a[i]);
puts("");
}
};
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
BigNum f[110];
f[0]=BigNum(1);
//f[0].print();
for(int i=1;i<=100;i++)
f[i]=f[i-1]*BigNum(4*i-2)/(i+1);
int n;
while(cin>>n&&n>0)f[n].print();
return 0;
}
POJ 2084 卡特兰数+高精度模板,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22295253