题解 P2532 【[AHOI2012]树屋阶梯】

· · 题解

卡特兰数新思路！

卡特兰数计算公式很多也很繁琐，今天就为大家展示一种很新颖的算法。

卡特兰数定义应该都懂，此处不做赘余。

先讲一下已有的计算公式：

设h(n)为catalan数的第n+1项，令h(0)=1,h(1)=1，

  1. catalan数满足递推式：h(n)= h(0) h(n-1)+h(1) h(n-2) + ... + h(n-1) * h(0) (n>=2)

例如：h(2)=h(0) h(1)+h(1) h(0)=1 1+1 1=2

h(3)=h(0) h(2)+h(1) h(1)+h(2) h(0)=1 2+1 1+2 1=5

  1. 另类递推式：

    h(n)=h(n-1) (4 n-2)/(n+1);

递推关系的解为：h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为：h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

但是很多时候这些递推式都是不可行的，因为数很大时要涉及取余运算，这时就有x%p==0的情况，于是answer=0，就会很快乐的wa掉。

我自己的方法：

相信大家知道有很多例子都符合卡特兰数列，于是小编给大家带来了题型汇总。

这样来说只要找出一个例子证明就好了，我选的是第二个，路径问题。

如图所示：

我想从最上面的节点走下来，只能向下或者向右，也就是说某个点只能由上面或者左面延伸过来。很显然的dp（如果还不懂的话参考数字三角形），那么到达某个点的方案数=左边点的方案数+右边点的方案数。

动态转移方程： f[i]=f[i]+f[i-1];

f[i]表示到达每一行第i个点的方案数。

当然这个题需要高精：

奉上简单明了的代码叭：

#include<iostream>
#include<stdio.h>
using namespace std;
int f[550][500];//f[i][j]表示第i个数的第j位。 
int len=1;
void add(int u)
{
    for(int i=1;i<=len;i++)
        f[u][i]=f[u-1][i]+f[u][i];
    for(int i=1;i<=len;i++)
    {
        f[u][i+1]+=f[u][i]/10;
        f[u][i]%=10;
    }
    if(f[u][len+1])len++;
}
int main()
{
    int n,p;
    cin>>n;
    f[1][1]=1;
    for(int i=2;i<=n+1;i++)
        for(int j=1;j<=i;j++)
            add(j);
    for(int i=len;i>0;i--)
        cout<<f[n][i];
}