题目

电影院卖电影票，但是没有零钱找，票价一张 5 元，买票的人为 n 个持有 5 元，m 个持
有 10 元，求解出可能的买票序列的个数，使得电影院能够将票卖完。

解题思路

买票问题是卡特兰数的经典问题之一。
持有5块钱的人每次买票的时候不需要找零，并且可以帮助到后面持有10块钱的人找零。而对于持有10块钱的人每次买票的时候需要找零，但是10块钱对后面的找零没有任何帮助。
所以。相对于每个持有10块钱的人都需要和一个持有五块钱的人进行匹配，可以将持有五块钱的人标记为-1，而持有10块钱的人标记为+1，这又相当是进出栈问题。
不同的是，此处m不一定与n相等，并且排队序列要考虑先后，例如两个人都持有五块钱他们交换位置会产生两种不同的排队序列。所以可以得到(C(m+n,n)-C(m+n,n-1))*n!*m!
最后为了使结果可以正确输出，int 和long long的范围明显是不够的，所以我选择将其存在vector容器中。

运行结果

源代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//乘法
vector<int>mul(vector<int>a, int b) {
	vector<int>c;
	int t = 0;
	for (int i = 0; i < a.size(); i++) {
		t = t + a[i] * b;
		c.push_back(t % 10);
		t = t / 10;
	}
	while (t) {
		c.push_back(t % 10);
		t = t / 10;
	}
	return c; 

}
//除法
vector<int>div(vector<int>& A, int b, int& r) {
	vector<int>c;
	r = 0;
	for (int i = A.size() - 1; i >= 0; i--) {
		r = r * 10 + A[i];
		c.push_back(r / b);
		r = r % b;
	}
	//倒转
	reverse(c.begin(), c.end());
	while (c.size() > 1 && c.back() == 0) {
		c.pop_back();
	}
	return c;
}
int main() {
	int n, m;
	cin >> n >> m;
	//当五块钱比十块钱少的时候，不存在合法情况
	if (n < m)
	{
		cout << "不存在合法情况！\n";
		return 0;
	}
	int r;
	vector<int> res;//储存结果的容器
	res.push_back(1);
	// 卡特兰数	(C(n+m,n) - C(n+m,n-1)) * n! * m!
	for (int i = 2; i <= n + m; i++) {
		res = mul(res, i);
	}
	res = mul(res, n + 1 - m);
	res = div(res, n + 1, r);
	for (int i = res.size() - 1; i >= 0; i--) {
		printf("%d", res[i]);
	}
	return 0;
}