hdu 1023 Train Problem II 卡塔兰数 栈

缘起

【1】中已经论述过卡塔兰数了. 本文搞道题目来玩玩~ hdu 1023 Train Problem II

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
计算卡塔兰数. 

【输入】
每行一个n

【输出】
第n个卡塔兰数

【样例输入】
1
2
3
10

【样例输出】
1
2
5
16796

【限制】
1s

显然, n可达100, 所以一定要使用高精度来计算卡塔兰数. 妈蛋，特别鄙视那些用java过的（java有BigInteger类，不过要是比赛，我也用java过~ ^_^） 下面的代码直接套用了【3】中的高精度模板, 但是事实证明, 【3】中封装的大整数类并不是太高效.

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
//#define LOCAL

typedef long long LL;

using namespace std;

class bigint // 大整数类
{
public:
	bigint(LL a) // 用long long新建bigint, 注意, long long 的范围是 10^19, 而且科学计数法的最高位还是9, 这就是为什么我们要选择long long 作为大整数的一节的原因. 因为做大整数乘法的时候 10^9*10^9=10^18 也不会超出long long 的范围
	{
		while(a) num.push_back(a%BASE),a/=BASE;
	}

	bigint(){};

	bigint(string s) // 用 字符串 构造大整数, 例如输入的字符串是 "1034004543543", 我们要将其存储为  004543543-->1034, 其中num[0]=004543543, num[1] = 1034
	{
		int n = s.length();
		for (int i = n-1; i>=0; i-=BASE_LEN) // 从高位开始构建
		{
			int j = max(0, i-BASE_LEN+1); // 则参与本次vector节点构建的字符是[j,...,i]
			LL t = 0;
			while(j<=i)
			{
				t = t*10+s[j]-'0'; // 洪特规则, 求出[j,...,i]表示的long long
				j++;
			}
			num.push_back(t);
		}
	}

	string toString() // 将大整数转为字符串输出(方便结果输出)
	{
		if (!num.size())
		{
			return "0";
		}
		stringstream ss;
		bool flag = true; // 是否在输出vector的栈顶元素? (它是大整数的最高位部分)， 之所以要区分是因为栈顶元素是不能补0的
		while(!num.empty())
		{
			if (flag)
			{
				ss << num.back();
				flag = false;
			}
			else
			{
				ss << setw(BASE_LEN) << setfill('0') <<num.back(); // 熟练使用STL 能极大减少编码的复杂度(而且看上去会很优雅)
			}
			num.pop_back();
		}
		return ss.str();
	}

	static bigint add(const bigint &a,const bigint &b) // 大整数加法 a+b(a,b皆非负), 其实就是小学生加法, 复杂度是O(n)的, 比字符串版本的大整数加法要快, 因为这里使用BASE_LEN作为一节, 所以其实一次做9位数加法（而且long long相加很快）, 即常数优化的.效率更高
	{
		bigint ans;
		for (LL i =0, carry=0; ; i++) // 注意, 大整数的结构是 num 的栈顶元素存储高位, 所以要从低位相加, carry 是上一步相加结果的进位(即i-1)
		{
			if (!carry && i>=a.num.size() && i >= b.num.size()) break; // 如果a和b都没有弹药了, 而且上一步并没有发生进位
			if (i<a.num.size()) // 如果a还有弹药
			{
				carry += a.num[i];
			}
			if (i<b.num.size()) // 如果b还有弹药
			{
				carry += b.num[i];
			}
			ans.num.push_back(carry%BASE);
			carry /= BASE; // 作为a.num[i+1]和b.num[i+1]的进位
		}
		return ans;
	}

	static bigint substract(const bigint &a,const bigint &b) // 高精度减法 a-b, 这里假设 a>=b, 复杂度是 O(N)
	{
		bigint ans;
		unsigned int i; // 注意, 因为size() 返回的是无符号整数, 所以这里最好使用unsigned int
		if (!b.num.size())
		{
			return a;
		}
		for (i = 0; i<b.num.size();i++)
		{
			ans.num.push_back(a.num[i]-b.num[i]); // 可能为负值
		}
		for (; i<a.num.size();i++)
		{
			ans.num.push_back(a.num[i]); // 把a剩下的塞进去
		}
		for (i = 0; i<ans.num.size()-1;i++) // 从ans的低位开始扫描负值, 即处理小学生减法之借位
		{
			if (ans.num[i]<0)
			{
				ans.num[i]+=BASE;
				ans.num[i+1]--; // 借位
			}
		}
		while(!ans.num.empty()&&!ans.num.back()) // 删除无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static int cmp(const bigint &a, const bigint &b) // 大于b返回1, 等于b返回0,小于b返回-1
	{
		if (a.num.size() != b.num.size())
		{
			return a.num.size()< b.num.size()?-1:1;
		}
		for (int i = a.num.size()-1; ~i; i--)
		{
			if (a.num[i]!=b.num[i])
			{
				return a.num[i]<b.num[i]?-1:1;
			}
		}
		return 0;
	}

	static bigint multiply(const bigint &a, const bigint &b) // 非负大整数乘法 a*b 复杂度 O(n^2)
	{
		bigint ans(vector<LL>(a.num.size()+b.num.size(),0)); // m位*n位最多m+n位,最少m+n-1位
		for (unsigned int i = 0; i< a.num.size(); i++)
		{
			for (unsigned int j =0; j<b.num.size();j++)
			{
				ans.num[i+j]+=a.num[i]*b.num[j];  // ans[i+j]的来源不止一个, 例如 ans[3]可以是 a[1]*b[2]也可以是a[2]*b[1]
				ans.num[i+j+1]+=ans.num[i+j]/BASE; // 进位
				ans.num[i+j]%=BASE;
			}
		}
		while(!ans.num.empty() && !ans.num.back()) // 去掉无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static bigint pow(bigint &a, int &b) // 求a^b, b是整型(已经够大了)
	{
		bigint ans(vector<LL>(1,1)); // ans=1
		while(b) // 快速幂
		{
			if (b&1)
			{
				ans = multiply(ans, a);
			}
			if (b>1)
			{
				a = multiply(a,a);
			}
			b>>=1;
		}
		return ans;
	}

	static bigint div(bigint &a,bigint &b)//非负大数相除a/b
	{
		int tmp;
		if ((tmp=cmp(a,b))!=1)
		{
			if (!tmp) // 如果a==b, 则 a 减去b变成0
			{
				a = bigint(vector<LL>(1,0));
			}
			bigint ans(vector<LL>(1,tmp?0:1));
			return ans;
		}
		int size_a=a.num.size(),size_b=b.num.size();//注意,此时a>b
		bigint ans;//m位除以n位(m>=n)最多m-n+1位,最少m-n位,但是这里不能预设多少位,因为除法与加减乘都不一样,它是从高位开始算的而其它三种是从低位开始算的
		for (int i = size_a-size_b; ~i; i--)
		{
			LL q=0;//每次除得的商
			ok(a,b,i,q);
			ans.num.push_back(q);			
		}
		reverse(ans.num.begin(),ans.num.end());//必须倒序存储
		while(!ans.num.empty() && !ans.num.back()) // 去掉无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static bigint res(bigint &a, bigint &b) // 高精度计算a%b
	{
		div(a,b);
		return a;
	}

	bool iszero()
	{
		bigint zero("0");
		return !num.size() || !cmp(*this, zero);
	}

	static bigint fac(int n) // 高精度计算 n!
	{
		bigint ans(vector<LL>(1,1));//ans=1
		for (int i = 2; i <= n; i++) ans=multiply(ans,bigint(vector<LL>(1,i)));
		return ans;
	}
private:
	const static int BASE_LEN=9,BASE=1000000000;// 10亿为基数
	vector<LL> num; // 构建大整数是这样的, 比如1034004543543, 在我们的bigint类中存储为  004543543-->1034, num[0]=004543543, num[1] = 1034
	bigint(vector<LL> num):num(num){} //使用一个vector构建大整数
	static void ok(bigint &a,bigint b,int i,LL &q)
	{			
		for (int j = 0; j < i; j++)	b.num.insert(b.num.begin(),0);//首先要给b补i个段的0
		int t = cmp(a,b);
		if (!~t) return; // 如果 a<b 则返回(q就是0)
		if (!t) // 如果 a==b
		{
			a = bigint(vector<LL>(1,0));
			q = 1;
			return;
		}
		LL k;
		bigint tmp_b;
		while(~t) // 只要 a >=b
		{
			for (k = 1, tmp_b = b; ~cmp(a, tmp_b); k*=10, tmp_b=multiply(tmp_b, bigint(vector<LL>(1,10)))) // 这里可以考虑 a=999减去b=10, 减去tmp_b=10(初始化为b),tmp_b=100,得到a=889，而再减tmp_b=1000的时候减不动了, 但是889依旧大于b, 所以要再来一轮——减去10,减去100, 得779. 这样比999每次减去10快多了,这可以看做是一个优化
			{
				q+=k;
				a = substract(a, tmp_b);
			}
			t = cmp(a,b);
		} // 最后 a<b
	}
};

bigint ans[105];

void catalan()
{
	ans[1] = bigint(1LL);
	for (LL i = 2; i<=100; i++)
	{
		ans[i] = bigint::multiply(ans[i-1], bigint(i*4-2));
		ans[i] = bigint::div(ans[i], bigint(i+1));
	}
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int x;
	catalan(); // 递推进行预处理
	while(~scanf("%d", &x))
	{
		cout <<ans[x].toString() << endl;
	}
	return 0;
}

但是遗憾的事情是上面的板子貌似速度比较慢, 而且比赛的时候你不可能写上面那么复杂的大数板子，所以必须要吸取其中的思想精华， 仿照【2】的思想, 试过了，第100个卡塔兰数是57位的, 而一个long long是18位的, 所以4个long long足够了. 但是考虑到除法, 需要使用8个int模拟, 即使用 LL [8] 来保存结果。BASE=1e9, 遂再写一版

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
//#include "stdafx.h"
#include <iostream>
#include <stdio.h>
using namespace std;
#include <iomanip>
//#define LOCAL

typedef long long LL;

LL ans[105][8], BASE=1e9; // ans[i]保存了第i个catalan数, ans[i][0],ans[i][1],ans[i][2], ans[i][3] 保留了从低位到高位

void catalan()
{
	ans[1][0] = 1; // 第一个卡塔兰数
	for (LL i = 2, m, d; i<=100; i++)
	{
		m = 4*i-2, d = i+1; // 要乘以m再除以d
		for (LL j = 0,carry = 0; j<8; j++)
		{
			ans[i][j] = ans[i-1][j]*m + carry;
			carry = ans[i][j]/BASE; // 进位
			ans[i][j]%=BASE;
		} // 乘以m
		for (LL j = 7, r=0, t; ~j; j--)
		{
			t =  r*BASE + ans[i][j];
			ans[i][j] = t /d;
			r = t%d;
		} // 除以d
	}
}

void print(int x) // 打印第x个卡塔兰数ans[x]
{
	bool flag = false;
	for (int i = 7; ~i; i--)
	{
		if (ans[x][i])
		{
			if (flag)
			{
				cout << setfill('0') << setw(9) << ans[x][i]; // 中间的0是不能漏掉的
			}
			else if (ans[x][i])
			{
				flag = true;
				printf("%lld", ans[x][i]);
			}
		}
	}
	puts("");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int x;
	catalan(); // 递推进行预处理
	while(~scanf("%d", &x))
	{
		print(x);
	}
	return 0;
}

ac情况

Status Accepted
Memory 1400kB
Length 1110
Lang G++
Submitted 2019-10-07 21:09:01
Shared
RemoteRunId 30793389

这一版不仅代码短, 而且效率高. 美滋滋~ 嘿嘿

所以如果你知道了最大的结果的位数是多少, 就没必要使用【3】中那个板子——太重了. 可以使用LL模拟即可.

参考

【1】https://yfsyfs.github.io/2019/05/24/Catalan%E6%95%B0/

【2】https://yfsyfs.github.io/2019/08/27/poj-3181-Dollar-Dayz-%E9%AB%98%E7%B2%BE%E5%BA%A6-dp/

【3】https://yfsyfs.github.io/2019/08/08/poj-1001-Exponentiation-%E9%AB%98%E7%B2%BE%E5%BA%A6%E4%B9%98%E6%B3%95%E4%B9%8Bkaratsuba%E7%AE%97%E6%B3%95/