問題#
入力形式：
1つの正の整数N（1<=N<=500）、階段の高さを表します。
出力形式：
構築方法の数を表す1つの正の整数。（注：構築方法の数は非常に大きくなる可能性があります）
分析#
人肉打表で規則を見つける厳密に証明したところ、これはカタラン数であることがわかりました。
そして 500 項目まで求める必要があります #(スプレー)
したがって、これは優れた高精度のボードでもあります。
コード#
まずは高精度部分（2 つのボードの 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;
}