AcWing 130. 火车进出栈问题

进出栈问题"/>

AcWing 130. 火车进出栈问题

AcWing 130. 火车进出栈问题

一列火车n节车厢，依次编号为1,2,3,…,n。

每节车厢有两种运动方式，进栈与出栈，问n节车厢出栈的可能排列方式有多少种。

输入格式
输入一个整数n，代表火车的车厢数。

输出格式
输出一个整数s表示n节车厢出栈的可能排列方式数量。

数据范围
1≤n≤60000
输入样例：

3

输出样例：

5

首先我们把入栈叫做’+’,出栈叫做’-’，然后我们开始分析。
一共有这五种情况。
+ + + − − − 321 +++--- 321 +++−−−321
+ − + − + − 123 + - +-+- 123 +−+−+−123
+ − + + − − 132 +-++-- 132 +−++−−132
+ + − − + − 213 ++--+- 213 ++−−+−213
+ + − + − − 231 ++-+-- 231 ++−+−−231
一共五种情况，我们发现一个问题，每到第i位，’+‘的数量一定不少于’-‘因为先进栈，然后才出栈，所以’+’>=’-'这就很类似于一个问题。Acwing 889. 满足条件的01序列然后这个代码不是很好写，而且很有难度，用到了高精度算法还有压位。

用到了数论的x的阶乘x!的质因数p有
res=x/p+x/p²+x/p³+…
于是代码如下。

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;const int N=160010;
int cnt;
int primes[N],sum[N];
bool st[N];void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}int get(int n, int p)
{int res = 0;while (n){res += n / p;n /= p;}return res;
}void div(vector<int> &a,int b)
{int t=0;for(int i=a.size()-1;~i;i--){t=t*10000+a[i];a[i]=t/b;t%=b;}while(a.size()>1&&!a.back()) a.pop_back();return;
}void mul(vector<int> &a,int b)
{int t=0;for(int i=0;i<a.size();i++){t+=a[i]*b;a[i]=t%10000;t/=10000;}while(t) a.push_back(t%10000),t/=10000;
}int main(void)
{int a,b;cin>>b;a=2*b;get_primes(a);for(int i=0;i<cnt;i++){int p=primes[i];sum[i]=get(a,p)-2*get(b,p);}//exit(0);vector<int> s;s.push_back(1);for(int i=0;i<cnt;i++){for(int j=0;j<sum[i];j++)mul(s,primes[i]);}div(s,b+1);printf("%d",s.back());for(int i=s.size()-2;i>=0;i--)printf("%04d",s[i]);
}

这个代码写的的确不易，之前写了很多代码，都没有AC,压位了才成功AC