n0867,破火诀怎么做,步步惊魂电影
描述
一列火车n节车厢,依次编号为1,2,3,…,n。每节车厢有两种运动方式,进栈与出栈,问n节车厢出栈的可能排列方式有多少种。
输入格式
一个数,n(n<=60000)
输出格式
一个数s表示n节车厢出栈的可能排列方式
样例输入1
3
样例输出1
5
样例输入2
50
样例输出2
1978261657756160653623774456
题解:
......,答案即为卡特兰数,可是窝的高精跑的太慢了qwq(被python代码吊起来打),所以这并不是std。
这里有一种非常精妙的球卡特兰数的方法,就是枚举中间的质数,算出每个质数出现了多少次,然后高精度乘法即可
#include <bits/stdc++.h> #define int long long using namespace std; int n,ans[1200000],len=1,p[1200000],c[1200000],tot; bool vis[1200000]; void jing(int x) { for(int i=1;i<=len;i++) ans[i]*=x; len+=6;//最多加六位(*的数小于等于n*2) for(int i=1;i<=len;i++) { ans[i+1]+=ans[i]/10; ans[i]%=10; } while(!ans[len]) len--; } signed main() { cin>>n; ans[1]=1; for(int i=2;i<=n*2;i++) if(!vis[i]) { p[++tot]=i; for(int j=i;j<=120000;j+=i) vis[j]=1; }//埃氏筛 for(int i=1;i<=tot;i++) { int now=p[i]; while(now<=n*2) {//c[i]指出现的个数 c[i]+=n*2/now-n/now-(n+1)/now; now*=p[i]; } while(c[i]--) jing(p[i]); } for(int i=len;i>=1;i--) cout<<ans[i]; return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论