P2532 [AHOI2012]树屋阶梯（数&高精度）

题目传送门

思路：卡特兰数的变形，可根据包含直角点的矩形覆盖的阶梯点的位置进行加法原理，然后对每个情况进行乘法原理，可以得到卡特兰数的递推式的形式。

根据左上角阶梯的方案数右下角阶梯形的方案数该情况方案数
由上图可知：图1为，图2为,图3为后面的图依次类推。

得到： 为递推式。

图片说明
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct num{
    int a[N],l;
}ans;
int n;
void multi(num &b,int x){  //高精 乘 低精 
    int p=0;
     for(int i=1;i<=b.l;i++){
           b.a[i]=b.a[i]*x+p;
           p=b.a[i]/10;
           b.a[i]%=10;
     }
     while(p){
         b.a[++b.l]=p;
         p/=10;
         b.a[b.l]%=10;
     }
}
void div(num &b,int x){ //高精 除 低精 
    int p=0;
    for(int i=b.l;i>=1;i--){
        p=p*10+b.a[i];
        b.a[i]=p/x;
        p%=x;
    }
    while(!b.a[b.l]) b.l--;
}
int main(){
    scanf("%d",&n);
    ans.a[1]=ans.l=1;
    for(int i=2;i<=n;i++) multi(ans,i+n);
    for(int i=2;i<=n;i++) div(ans,i);
    for(int i=ans.l;i>=1;i--)
         printf("%d",ans.a[i]);
    return 0;
}