题目描述

暑假期间，小龙报名了一个模拟野外生存作战训练班。

训练的第一个晚上，教官就给他们出了个难题。

由于地上露营湿气重，必须选择在高处的树屋露营。

小龙分配的树屋建立在一颗高度为 N+1 尺的大树上，正当他发愁怎么爬上去的时候，发现旁边堆满了一些空心四方钢材（如图 1.1）。

经过观察和测量，这些钢材截面的宽和高大小不一，但都是 1 尺的整数倍，教官命令队员们每人选取 N 个空心钢材来搭建一个总高度为 N 尺的阶梯来进入树屋，该阶梯每一步台阶的高度为 1 尺，宽度也为 1 尺。

如果这些钢材有各种尺寸，且每种尺寸数量充足，那么小龙可以有多少种搭建方法？

样例

输入 3
输出 5

为什么是卡特兰数呢？

先看图

将一个比较大的阶梯可以拆成两个阶梯加上一个合法钢材,这是必然可以的!!
左上方是i级阶梯,右下方是n-i-1级阶梯,f[i]表示搭建i级阶梯需要i个钢材的方案数
然后就是运用乘法原理计算一下左上方的阶梯方案数*右下方的阶梯方案数,于是就有
f [ n ]=sigma(f [ i ] * f [ n-i-1 ]) (0 <= i < n);
这便是卡特兰数的递推公式,有时候不会证明可以从定义出发!!!

虽然我是看到3=>5直接卡特兰了QWQ
附上代码

#include<iostream>
#include<cstdio>
using namespace std;

const int N =2010;

int primes[N],cnt;
bool st[N];
int a[N],b[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[i*primes[j]]=true;
            if(i%primes[j]==0)  break;
        }
    }
}
int get(int n,int p)//n!中p的次数
{
    int s=0;
    while(n)    n/=p,s+=n;
    return s;
}
void mul(int a[],int &len,int b)//a=a*b的高精度
{
    int t=0;
    for(int i=0;i<len;i++)
    {
        t+=a[i]*b;
        a[i]=t%10;
        t/=10;
    }
    while(t)
    {
        a[len++]=t%10;
        t/=10;
    }
}

int C(int a,int b,int c[])
{
    int len=1;
    c[0]=1;
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        int s=get(a,p)-get(b,p)-get(a-b,p);
        while(s--)  mul(c,len,p);
    }
    return len;
}

void sub(int a[],int a1,int b[],int b1)
{
    for(int i=0,t=0;i<a1;i++)
    {
        a[i]=a[i]-t-b[i];
        if(a[i]<0) a[i]+=10,t=1;
        else t=0;
    }
}

int main()
{
    init(N-1);

    int n,m;
    scanf("%d",&n);
    m=n;
    int a1=C(n+m,m,a);
    int b1=C(n+m,m-1,b);

    sub(a,a1,b,b1);

    int i=a1-1;//从第a1-1位开始判断有没有0
    while(!a[i]&&i) i--;

    while(i>=0) cout<<a[i--];
    return 0;
}

熟练应用组合数IV模板和卡特兰高精度模板,证明不一定要会,但需熟练模板