P2532 [AHOI2012]树屋阶梯 卡特兰数

这个题是一个卡特兰数的裸题，为什么呢？因为可以通过划分来导出递推式从而判断是卡特兰数，然后直接上公式就行了。卡特兰数的公式见链接。

https://www.luogu.org/problemnew/solution/P2532

代码实现不难，就是一个高精乘|除低精。

题干：

题目描述

输入输出格式

输入格式：

一个正整数N（1<=N<=500），表示阶梯的高度。

输出格式：

一个正整数，表示搭建方法的个数。（注：搭建方法的个数可能很大）

输入输出样例

输入样例#1：

3

输出样例#1：

5

说明

40%的数据：1<=N<=20

80%的数据：1<=N<=300

100%的数据：1<=N<=500

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

struct node

{

    int l,a[];

};

node init()

{

    node h;

    h.l = ;

    h.a[] = ;

    return h;

}

void mu(node &m,int b)

{

    duke(i,,m.l)

    {

        m.a[i] *= b;

    }

    duke(i,,m.l)

    {

        if(m.a[i] >= )

        {

            m.a[i + ] += m.a[i] / ;

            m.a[i] %= ;

            if(i == m.l)

            m.l++;

        }

    }

    // int tot = 1;

    while(m.a[m.l] > )

    {

        m.a[m.l + ] += m.a[m.l] % ;

        m.a[m.l] %= ;

        m.l++;

    }

}

node dev(node m,int b)

{

    node h;

    int tot = ;

    lv(i,m.l,)

    {

        tot = tot *  + m.a[i];

        h.a[i] = tot / b;

        tot %= b;

    }

    h.l = m.l;

    while(h.a[h.l] == )

    h.l--;

    return h;

}

void output(node m)

{

    lv(i,m.l,)

    {

        printf("%d",m.a[i]);

    }

    return;

}

int n;

int main()

{

    node l;

    l = init();

    read(n);

    duke(i,n + ,n * )

    {

        mu(l,i);

    }

    duke(i,,n)

    {

        l = dev(l,i);

    }

    // l = dev(l,6);

    output(l);

    return ;

}