高精度 x卡特兰数 （数学）进出栈序列问题

链接：https://ac.nowcoder.com/acm/contest/1005/B 来源：牛客网

进出栈序列问题 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 一列火车n节车厢，依次编号为1,2,3,…,n。每节车厢有两种运动方式，进栈与出栈，问n节车厢出栈的可能排列方式有多少种。 输入描述:

一个数，n(n≤60000)n (n \leq 60000)n(n≤60000)

输出描述:

一个数s表示n节车厢出栈的可能排列方式

LINK<好艰难诶>

自己瞎写有错请指出，Thanks♪(･ω･)ﾉ高精度x卡特兰数（C(n ,2n)/(n+1)） 数学+++++首先知道这是卡特兰数的模型答案就是C（n,2n）/(n+1)->也就是（2n）!/[(n!*n!) (n+1)]对于组合数如果单方面的考虑处理分子/分母 数的范围很大 很可能会超时->考虑分解质因数举个例子组合数C(3,6)=(6 * 5 * 4)/(3 * 2 * 1)=>2^ 2 * 3^ 0 * 5^ 1也就是考虑（2n）!里面有 2的x1次 ，3的x2次，5的几次…以及（n）!里面有 2的y1次 ，3的y2次，5的几次…答案就应该是[2^(x1-2*y1) * 3 ^(x2-y2 * 2)…]/(n+1)------------<为什么y1 ,y2要乘2，因为分母是n! * n!>这里的小知识 关于求n!里面的2的几次之类就是下面的get函数了

[n/2]+[n/（2 * 2 ）]+[n/(2 * 2 * 2)]…括号下取整 类似求n!有p的几次[n/p]+[n/（p* p ）]+[n/(p * p * p)]…括号下取整

#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=120010; int prime[N],cnt;bool st[N];ll power[N]; void getpr(int n)//筛素数 { for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; for(int j=i*2;j<=n;j+=i) { st[j]=true; } } } } int get(int n,int p)//判n!里面有p的几次 { int s=0; while(n) { s+=n/p; n/=p; }return s; } void multi(vector<ll>&a,int b)//高精度 { ll t=0; for(int i=0;i<a.size();i++) { a[i]=1ll*a[i]*b+t; t=a[i]/1000000000; a[i]%=1000000000; } while(t) { a.push_back(t%1000000000); t/=1000000000; } } void out(vector<ll>&a) { printf("%lld",a.back()); for(int i=a.size()-2;i>=0;i--) { printf(" lld",a[i]);//压位 } puts(""); } int main() { int n; scanf("%d",&n); getpr(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;//考虑解决剩下的除数n+1 for(int i=0;i<cnt&&prime[i]<=k;i++) { int p=prime[i],s=0; while(k%p==0) { s++; k/=p; }power[p]-=s; } vector<ll>res; res.push_back(1ll); for(int i=2;i<=n*2;i++) { for(int j=0;j<power[i];j++) { multi(res,i); } } out(res); }

T掉的码 ~~

#include<cstdio> using namespace std; const int N=600010; typedef long long ll; ll tt,ans[N]; inline void multi(int b) { ll t=0; for(register int i=0;i<=tt;i++) { ans[i]=ans[i]*b+t; t=ans[i]/1000000000; ans[i]%=1000000000; } while(t) { ans[++tt]=t%1000000000; t/=1000000000; } } inline void div(int b) { ll t=0; for(register int i=tt;i>=0;i--) { ans[i]+=t*1000000000; t=ans[i]%b; ans[i]/=b; } while(ans[tt]==0) { tt--; } } int main() { static int n;scanf("%d",&n); tt=0; ans[0]=1ll; for(register int i=n*2,j=1;j<=n;++j,--i) { multi(i); div(j); }div(n+1); printf("%lld",ans[tt]); for(register int i=tt-1;i>=0;i--) { printf(" lld",ans[i]); } puts(""); return 0; } 相关的栈的火车问题简单版