Problem#
Input Format:
A positive integer N (1<=N<=500), representing the height of the stairs.
Output Format:
A positive integer, representing the number of construction methods. (Note: The number of construction methods may be very large)
Analysis#
Through manual table lookup to find patterns rigorous proof, it is found that this is a Catalan number.
Then it is required to find the 500th term #(spray)
So this is also an excellent high-precision template.
Code#
First is the high-precision part (codemix of two templates)
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;
}
};
Then comes the Catalan number part,
The mysterious thing about this problem is that using recursion will result in RE in my case, but not on Luogu and cqyzoj...
Using recursion will result in TLE...
Correction: Using a too weird recursion
Recursive method (Formula 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);
}
"Too weird" recursive method (Formula 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];
}
(Declaration of k):
bigNum k[510]={(bigNum)1,(bigNum)1};
The following is the complete code
#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;
}