题目
1
2
3
4
5
6
7
| 输入格式：
一个正整数N（1<=N<=500），表示阶梯的高度。
输出格式：
一个正整数，表示搭建方法的个数。（注：搭建方法的个数可能很大）
|
分析
通过人肉打表找规律严格证明发现这是个卡特兰数
然后要求到第500项#(喷)
所以这同时也是个优秀的高精度板子
Code
首先是高精度部分（两个板子的codemix）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| 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）：
1
2
3
4
5
6
| 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）：
1
2
3
4
5
6
7
8
9
10
| bigNum ktl(int n){
for(int i=2;i<=n;++i){
for(int j=0;j<i;++j){
k[i]=k[i]+(k[j]*k[i-j-1]);
}
}
return k[n];
}
|
（k的声明）：
1
| bigNum k[510]={(bigNum)1,(bigNum)1};
|
以下为完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
| #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 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();
return 0;
}
|
