題目#
輸入格式：
一個正整數N（1<=N<=500），表示階梯的高度。
輸出格式：
一個正整數，表示搭建方法的個數。（注：搭建方法的個數可能很大）
分析#
透過人肉打表找規律嚴格證明發現這是一個卡特蘭數
然後要求到第 500 項 #(噴)
所以這同時也是一個優秀的高精度板子
Code#
首先是高精度部分（兩個板子的 codemix）
struct bigNum{
private:
short t[1005];int siz;
public:
bigNum(string a){
memset(t,0,sizeof(t));
int len=a.size();
for(int i=0;i<a.size();++i){
t[len-i]=a[i];
}
siz=len;
}
bigNum(void){
memset(t,0,sizeof(t));
siz=0;
}
bigNum(long long x){
memset(t,0,sizeof(t));
int ws=0;
while(x){
++ws;
int q=x%10;
x/=10;
t[ws]=q;
}
siz=ws;
}
void print(void){
for(int i=siz;i>=1;--i){
putchar(t[i]+'0');
}
putchar('\n');
}
int size(void){
return siz;
}
friend bigNum operator *(bigNum a,long long b){
bigNum c;
int len=a.size()+20,g=0;
for(int i=1;i<=len;++i){
c.t[i]=a.t[i]*b;
}
for(int i=1;i<=len;++i){
if(c.t[i]>9){
c.t[i+1]+=c.t[i]/10;
c.t[i]=c.t[i]%10;
}
}
while(len>1&&c.t[len]==0)--len;
c.siz=len;
return c;
}
friend bigNum operator *(long long b,bigNum a){
return a*b;
}
friend bigNum operator *(bigNum a,bigNum b){
bigNum c;
int len=a.size()+b.size();
for(int i=1;i<=a.size();++i){
for(int j=1;j<=b.size();++j){
c.t[i+j-1]+=(a.t[i]*b.t[j]);
}
}
for(int i=1;i<=len;++i){
if(c.t[i]>9){
c.t[i+1]+=c.t[i]/10;
c.t[i]=c.t[i]%10;
}
}
while(len>1 && c.t[len]==0)len--;
c.siz=len;
return c;
}
friend bigNum operator /(bigNum a,long long b){
bigNum c;
int k=a.size(),g=0;
for(int i=k;i>0;--i){
g=g*10+a.t[i];
c.t[i]=g/b;
g%=b;
}
while(k>1&&c.t[k]==0)--k;
c.siz=k;
return c;
}
friend bigNum operator /(long long b,bigNum a){
return a/b;
}
friend bigNum operator +(bigNum a,bigNum b){
bigNum c;
int g=0,k=max(a.size(),b.size());
for(int i=1;i<=k;i++){
c.t[i]=a.t[i]+b.t[i]+g;
g=c.t[i]/10;
c.t[i]%=10;
}
if(g>0){
c.t[++k]=g;
}
c.siz=k;
return c;
}
};
然後是卡特蘭數部分，
這道題很玄學的地方在於，用遞歸在我這裡會 RE，在洛谷和 cqyzoj 上就不會。。。
用遞推會超時。。。
更正：用太過詭異的遞推
遞歸求法（公式 2）：
bigNum ktl(int x){
if(x<=0)return 0;
if(x==1)return 1;
if(k[x].size())return k[x];
else return k[x]=(4*x-2)*ktl(x-1)/(x+1);
}
“太過詭異的” 遞推求法（公式 1）：
bigNum ktl(int n){
for(int i=2;i<=n;++i){
for(int j=0;j<i;++j){
// printf("%d %d\n",i,j);
k[i]=k[i]+(k[j]*k[i-j-1]);
//ans.print();
}
}
return k[n];
}
（k 的聲明）：
bigNum k[510]={(bigNum)1,(bigNum)1};
以下為完整代碼
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct bigNum{
private:
short t[1005];int siz;
public:
bigNum(string a){
memset(t,0,sizeof(t));
int len=a.size();
for(int i=0;i<a.size();++i){
t[len-i]=a[i];
}
siz=len;
}
bigNum(void){
memset(t,0,sizeof(t));
siz=0;
}
bigNum(long long x){
memset(t,0,sizeof(t));
int ws=0;
while(x){
++ws;
int q=x%10;
x/=10;
t[ws]=q;
}
siz=ws;
}
void print(void){
for(int i=siz;i>=1;--i){
putchar(t[i]+'0');
}
putchar('\n');
}
int size(void){
return siz;
}
friend bigNum operator *(bigNum a,long long b){
bigNum c;
int len=a.size()+20,g=0;
for(int i=1;i<=len;++i){
c.t[i]=a.t[i]*b;
}
for(int i=1;i<=len;++i){
if(c.t[i]>9){
c.t[i+1]+=c.t[i]/10;
c.t[i]=c.t[i]%10;
}
}
while(len>1&&c.t[len]==0)--len;
c.siz=len;
return c;
}
friend bigNum operator *(long long b,bigNum a){
return a*b;
}
friend bigNum operator *(bigNum a,bigNum b){
bigNum c;
int len=a.size()+b.size();
for(int i=1;i<=a.size();++i){
for(int j=1;j<=b.size();++j){
c.t[i+j-1]+=(a.t[i]*b.t[j]);
}
}
for(int i=1;i<=len;++i){
if(c.t[i]>9){
c.t[i+1]+=c.t[i]/10;
c.t[i]=c.t[i]%10;
}
}
while(len>1 && c.t[len]==0)len--;
c.siz=len;
return c;
}
friend bigNum operator /(bigNum a,long long b){
bigNum c;
int k=a.size(),g=0;
for(int i=k;i>0;--i){
g=g*10+a.t[i];
c.t[i]=g/b;
g%=b;
}
while(k>1&&c.t[k]==0)--k;
c.siz=k;
return c;
}
friend bigNum operator /(long long b,bigNum a){
return a/b;
}
friend bigNum operator +(bigNum a,bigNum b){
bigNum c;
int g=0,k=max(a.size(),b.size());
for(int i=1;i<=k;i++){
c.t[i]=a.t[i]+b.t[i]+g;
g=c.t[i]/10;
c.t[i]%=10;
}
if(g>0){
c.t[++k]=g;
}
c.siz=k;
return c;
}
};
bigNum k[510]={(bigNum)1,(bigNum)1};
/*bigNum ktl(int x){
if(x<=0)return 0;
if(x==1)return 1;
if(k[x].size())return k[x];
else return k[x]=(4*x-2)*ktl(x-1)/(x+1);
}*/
bigNum ktl(int n){
for(int i=2;i<=n;++i){
k[i]=(4*i-2)*k[i-1]/(i+1);
}
return k[n];
}
int main(void){
int n;
cin>>n;
ktl(n).print();
// bigNum a(123),b(45);
// (a*b).print();
return 0;
}