[数据结构与算法]AcWing 火车出栈问题 题解（栈 （可能有吧）+ 欧拉筛 + 卡特兰数 + 质因数分解 + 思路）

一道题花了五六个小时，可能是我太菜了，学到了好多东西（欧拉筛、卡特兰数、质因数分解）

解题思路：火车进出站–合法的加减号排列–通过合法的路径到达（n, n）–推出公式–利用质因数分解实现超级大数的快速运算–打王者去了，溜了溜了

原题链接：https://www.acwing.com/problem/content/description/132/
（AcWing可以看自己没过的每一个样例，个人觉得是个练题神器）

思路讲解链接（yxc yyds）：https://www.acwing.com/video/66/

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 6e4 + 10;

int st[N] * 2;
int prime[N*2], power[N*2];
int n;
int cnt;

int get(int n, int p){
	int s = 0;
	while(n){
		s += n / p;
		n /= p;
	}
	return s;
}

void get_prime(int n){
	st[1] = true;
	for(int i = 2; i <= n; i ++ ){
		if(!st[i]) prime[cnt ++ ] = i;
		for(int j = 0; j < cnt && prime[j] * i <= n; j ++ ){
			st[prime[j] * i] = true;
			if(i % prime[j] == 0) break;
		}
	}
}

void multi(vector<int> &res, int b){
	int t = 0;
	for(int i = 0; i < res.size(); i ++ ){
		res[i] = res[i] * b + t;
		t = res[i] / 10000;
		res[i] %= 10000;
	}
	while(t){
		res.push_back(t % 10000);
		t /= 10000;
	}
}
int main()
{
	scanf("%d", &n);
	get_prime(n * 2);

	for(int i = 0; i < cnt; i ++ ){
		int p = prime[i];
		power[p] = get(n * 2, p) - get(n , p) * 2;
	}
	
	int k = n + 1;
	for(int i = 0; i < cnt && k > 1; i ++ ){
		int s = 0;
		int p = prime[i];
		while(k % p == 0){
			s ++ ;
			k /= p;
		}
		power[p] -= s;
	}
	
	vector<int> res;
	res.push_back(1);
	
	for(int i = 0; i < cnt; i ++ ){
		int p = prime[i];
		for(int j = 0; j < power[p]; j ++ ){
			multi(res, p);
		}
	}
	printf("%d", res.back());
	for(int i = res.size() - 2; i >= 0; i -- ){
		printf("%04d", res[i]);		
	}
	return 0;
}