- Problem Description
- As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
- Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
- Output
- For each test case, you should output how many ways that all the trains can get out of the railway.
- Sample Input
- 1
- 2
- 3
- 10
- Sample Output
- 1
- 2
- 5
- 16796
解: 这题就是卡特兰数 (不过要用大数), 在以前的博客中写过: https://www.cnblogs.com/wz-archer/p/12433890.html
bing 巨的代码写的非常简洁: 传送门
我的代码:↓(参考了紫书大数)
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <map>
- using namespace std;
- typedef long long ll;
- const double inf=1e20;
- const int maxn=2e5+10;
- const int mod=1e9+7;
- struct BigInteger{
- static const int BASE=100000000;
- static const int WIDTH=8;
- vector<int>s;
- bool sign;
- size_t length;
- BigInteger(ll x=0){*this=x;}
- BigInteger(const string &x){*this=x;}
- BigInteger(const BigInteger &x){*this=x;}
- void cutLeadingZero(){
- while(s.back()==0&&s.size()!=1)s.pop_back();
- ll tmp=s.back();
- if(tmp==0)length=1;
- else{
- length=(s.size()-1)*WIDTH;
- while(tmp>0){
- length++;
- tmp/=10;
- }
- }
- }
- BigInteger &operator=(ll x){
- s.clear();
- if(x>=0)sign=true;
- else{
- sign=false;
- x=-x;
- }
- do{
- s.push_back(x%BASE);
- x/=BASE;
- }while(x>0);
- return *this;
- }
- BigInteger &operator=(const string &str){
- s.clear();
- sign=(str[0]!='-');
- int x,len=(str.size()-1-(!sign))/WIDTH+1;
- for(int i=0;i<len;i++){
- int End=str.size()-i*WIDTH;
- int start=max((sign)?0:1,End-WIDTH);
- sscanf(str.substr(start,End-start).c_str(),"%d",&x);
- s.push_back(x);
- }
- cutLeadingZero();
- return *this;
- }
- BigInteger &operator=(const BigInteger &tmp){
- s=tmp.s;
- sign=tmp.sign;
- length=tmp.length;
- return *this;
- }
- BigInteger abs()const{
- BigInteger ans(*this);
- ans.sign=true;
- return ans;
- }
- const BigInteger &operator+()const{return *this;}
- BigInteger operator-()const{
- BigInteger ans(*this);
- if(ans!=0)
- ans.sign=!ans.sign;
- return ans;
- return ans;
- }
- BigInteger operator+(const BigInteger &b)const{
- if(!b.sign)return *this-(-b);
- if(!sign)return b-(-*this);
- BigInteger ans;
- ans.s.clear();
- for(int i=0,g=0;;i++){
- if(g==0&&i>=(int)s.size()&&i>(int)b.s.size())break;
- int x=g;
- if(i<(int)s.size())x+=s[i];
- if(i<(int)b.s.size())x+=b.s[i];
- ans.s.push_back(x%BASE);
- g=x/BASE;
- }
- ans.cutLeadingZero();
- return ans;
- }
- BigInteger operator-(const BigInteger &b)const{
- if(!b.sign)return *this+(-b);
- if(!sign)return -((-*this)+b);
- if(*this<b)return -(b-*this);
- BigInteger ans;
- ans.s.clear();
- for(int i=0,g=0;;i++){
- if(g==0&&i>=(int)s.size()&&i>=(int)b.s.size())break;
- int x=g;
- g=0;
- if(i<(int)s.size())x+=s[i];
- if(i<(int)b.s.size())x-=b.s[i];
- if(x<0){
- x+=BASE;
- g=-1;
- }
- ans.s.push_back(x);
- }
- ans.cutLeadingZero();
- return ans;
- }
- BigInteger operator*(const BigInteger &b)const{
- int lena=s.size(),lenb=b.s.size();
- BigInteger ans;
- for(int i=0;i<=lena+lenb;i++){
- ans.s.push_back(0);
- }
- for(int i=0,g=0;i<lena;i++){
- g=0;
- for(int j=0;j<lenb;j++){
- ll x=ans.s[i+j];
- x+=(ll)s[i]*(ll)b.s[j];
- ans.s[i+j]=x%BASE;
- g=x/BASE;
- ans.s[i+j+1]+=g;
- }
- }
- ans.cutLeadingZero();
- ans.sign=(ans.length==1&&ans.s[0]==0)||(sign==b.sign);
- return ans;
- }
- /*
- BigInteger e(size_t n)const{
- int tmp=n%WIDTH;
- BigInteger ans;
- ans.length=n+1;
- n/=WIDTH;
- while(ans.s.size()<=n)
- ans.s.push_back(0);
- ans.s[n]=1;
- while(tmp--)ans.s[n]*=10;
- return ans*(*this);
- }
- BigInteger operator/(const BigInteger &b)const{
- BigInteger aa((*this).abs());
- BigInteger bb(b.abs());
- if(aa<bb)return 0;
- char *str=new char[aa.length+1];
- memset(str,0,sizeof(char)*(aa.length+1));
- BigInteger tmp;
- int lena=aa.length,lenb=bb.length;
- for(int i=0;i<lena-lenb;i++){
- tmp=bb.e(lena-lenb-i);
- while(aa>=tmp){
- str[i]++;
- aa=aa-tmp;
- }
- str[i]+='0';
- }
- BigInteger ans(str);
- delete[] str;
- ans.sign=(ans==0||sign==b.sign);
- return ans;
- }
- BigInteger operator%(const BigInteger &b)const{
- return *this-*this/b*b;
- }
- */
- BigInteger &operator++(){
- *this=*this+1;
- return *this;
- }
- BigInteger &operator--(){
- *this=*this-1;
- return *this;
- }
- BigInteger &operator+=(const BigInteger &b){
- *this=*this+b;
- return *this;
- }
- //+=,-=,*=,/=,%=
- bool operator<(const BigInteger &b)const{
- if(sign!=b.sign){
- return !sign;
- }else if(!sign&&!b.sign){
- return -b<-*this;
- }
- if(s.size()!=b.s.size())
- return s.size()<b.s.size();
- for(int i=s.size()-1;i>=0;i--){
- if(s[i]!=b.s[i])
- return s[i]<b.s[i];
- }
- return false;
- }
- bool operator>(const BigInteger &b)const{
- return b<*this;
- }
- bool operator<=(const BigInteger &b)const{
- return !(b<*this);
- }
- bool operator>=(const BigInteger &b)const{
- return !(*this<b);
- }
- bool operator!=(const BigInteger &b)const{
- return b<*this||*this<b;
- }
- bool operator==(const BigInteger &b)const{
- return !(b<*this)&&!(*this<b);
- }
- bool operator!(){return (bool)(*this==0);}
- friend ostream &operator<<(ostream &out,const BigInteger &x){
- if(!x.sign)out<<'-';
- out<<x.s.back();
- for(int i=x.s.size()-2;i>=0;i--){
- char buf[10];
- sprintf(buf,"%08d",x.s[i]);
- for(int j=0;j<(int)strlen(buf);j++){
- out<<buf[j];
- }
- }
- return out;
- }
- friend istream &operator>>(istream &in,BigInteger &x){
- string str;
- in>>str;
- size_t len=str.size();
- int start=0;
- if(str[0]=='-')start=1;
- if(str[start]=='\0')return in;
- for(int i=start;i<(int)len;i++){
- if(str[i]<'0'||str[i]>'9')
- return in;
- }
- x.sign=!start;
- x=str.c_str();
- return in;
- }
- };
- BigInteger a[110];
- int main(){
- ll n;
- a[0]=a[1]=1;
- for(int i=2;i<=100;i++){
- a[i]=0;
- }
- for(int i=2;i<=100;i++){
- for(int j=0;j<i;j++){
- a[i]=a[i]+(a[j]*a[i-j-1]);
- }
- //cout<<a[i]<<endl;
- }
- while(cin>>n){
- cout<<a[n]<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3451904.html