题目描述

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

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

输入样例：

3

输出样例：

5

算法1

把(n+1)当做高位除法进行运算，结果当位数高于50后就会出现错误。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10,mod = 1e8;
typedef long long LL;
int primes[N],co;
bool st[N];
void p(int n)
{
    co=0;   
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[co++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i % primes[j]==0) break;
        }
    }
}

int calc(int n,int pr)
{
    int s=0;
    while(n>0)
    {
        s+=n/pr;
        n/=pr;
    }
    return s;
}

vector<LL> mul(vector<LL> a,int b)
{
    vector<LL> c;
    LL t=0;
    for(int i=0;i<a.size();i++)
    {
        t+=a[i]*b;
        c.push_back(t%mod);
        t/=mod;
    }
    while(t)
    {
        c.push_back(t%mod);
        t/=mod;
    }
    return c;
}

vector<LL> div(vector<LL> a,LL b)
{
    LL t=0;
    vector<LL> c;
    for(int i=a.size()-1;i>=0;i--)
    {
        t=10*t+a[i];
        c.push_back(t/b);
        t=t%b;
    }
    reverse(c.begin(),c.end());
    while(c.size()>1 && c.back()==0) c.pop_back();
    return c;
}
int main()
{
        int a,b,n; 
        scanf("%d",&n);
        a = 2*n,b=n;
        p(a);
        int num[N];
        for(int i=0;i<co;i++)
        {
            int pr = primes[i];
            num[i] = calc(a,pr) - calc(b,pr) - calc(a-b,pr); 
        }
        vector<LL> ans;
        ans.push_back(1);
        for(int i=0;i<co;i++)
        {
            while(num[i]--) ans = mul(ans,primes[i]);
        }
        ans = div(ans,(LL)b+1);
        printf("%lld",ans.back());
        for(int i=ans.size()-2;i>=0;i--) printf("%08lld",ans[i]);
    return 0;
}

算法2 y总做法，压8位lld格式，速度很快

$$ 卡特兰数：f(n)=\frac{C_{2n}^{n}}{n+1}= C_{2n}^{n}-C_{2n}^{n-1}=\frac{2n!}{n!n!(n+1)} $$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 6e5+10,mod = 1e8;
typedef long long LL;
int primes[N],co;
bool st[N];
void p(int n)
{
    co=0;   
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[co++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i % primes[j]==0) break;
        }
    }
}

int calc(int n,int pr)
{
    int s=0;
    while(n>0)
    {
        s+=n/pr;
        n/=pr;
    }
    return s;
}

vector<LL> mul(vector<LL> a,int b)
{
    vector<LL> c;
    LL t=0;
    for(int i=0;i<a.size();i++)
    {
        t+=a[i]*b;
        c.push_back(t%mod);
        t/=mod;
    }
    while(t)
    {
        c.push_back(t%mod);
        t/=mod;
    }
    return c;
}

int main()
{
        int a,b,n; 
        scanf("%d",&n);
        a = 2*n,b=n;
        p(a);
        int num[N];
        for(int i=0;i<co;i++)
        {
            int pr = primes[i];
            num[i] = calc(a,pr) - 2*calc(b,pr); 
        }
        int k=n+1;
        for(int i=0;i<co && primes[i]<=k;i++)
        {
            int pr = primes[i],sum=0;
            while(k%pr==0)
            {
                sum++;
                k/=pr;
            }
            num[i]-=sum;
        }

        vector<LL> ans;
        ans.push_back(1);
        for(int i=0;i<co;i++)
        {
            while(num[i]--) ans = mul(ans,primes[i]);
        }
        printf("%lld",ans.back());
        for(int i=ans.size()-2;i>=0;i--) printf("%08lld",ans[i]);
    return 0;
}