P2532 [AHOI2012]树屋阶梯

题目：P2532 [AHOI2012]树屋阶梯

思路：

打表之后不难看出是裸的Catalan数。简单证明一下：
对于任意一种合法方案，都可以表示为在左下角先放一个\(k*(n+1-k),k\in[1,n]\)的矩形，再在矩形的上边和右边分别放\(k-1\)阶台阶和\(n-k\)阶台阶。
例如下图（从luogu题解中盗的图...）：
在左下角先放了一个\(2*3\)的矩形，之后在矩形上边放\(1\)阶台阶，在矩形右边放\(2\)阶台阶。

不难看出矩形上边和右边两部分独立，只要枚举左下矩阵长度，对每种矩形，把上边和右边的方案数相乘（乘法原理），再把不同矩形长度得到的答案相加（加法原理）就能得到总方案数。
设\(h(n)\)为n阶台阶方案数，得到递推式\(h(n)=\sum_{k=1}^nh(k-1)*h(n-k)\),就是Catalan数。
计算时分解质因数即可。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 5000,base=10000,power=4;
int n,tot,p[N],mindiv[N],cnt[N];
struct bigint{
    int len,d[N];
    inline bigint (){
        memset(d,0,sizeof(d));
        len=1;
    }
    inline bigint(int num){
        len=1;
        d[1]=num;
    }
    void clean(){
        while(len>1&&!d[len]) --len;
    }
    inline bigint operator * (const bigint &b)const{
        bigint c;
        c.len=len+b.len;
        for(int i=1;i<=len;++i) for(int j=1;j<=b.len;++j)
            c.d[i+j-1]+=d[i]*b.d[j],c.d[i+j]+=c.d[i+j-1]/base,c.d[i+j-1]%=base;
        c.clean();
        return c;
    }
    inline void print(){
        clean();
        printf("%d",d[len]);
        for(int i=len-1;i;--i) printf("%0*d",power,d[i]);
    }
};
void Prime(){
    for(int i=2;i<=2*n;++i){
        if(!mindiv[i]) mindiv[i]=p[++tot]=i;
        for(int j=1;j<=tot;++j){
            if(i*p[j]>2*n||p[j]>mindiv[i]) break;
            mindiv[i*p[j]]=p[j];
        } 
    }
}
void add(int num){
    while(num^1){
        ++cnt[mindiv[num]];
        num/=mindiv[num];
    }
}
void del(int num){
    while(num^1){
        --cnt[mindiv[num]];
        num/=mindiv[num];
    }
}
bigint quickpow(int a,int b){
    bigint res=1,c=a;
    while(b){
        if(b&1) res=res*c;
        c=c*c;
        b>>=1;
    }
    return res;
}
bigint Catalan(int n){
    for(int i=n+2;i<=2*n;++i) add(i);
    for(int i=1;i<=n;++i) del(i);
    bigint res=1;
    for(int i=1;i<=tot;++i) res=res*quickpow(p[i],cnt[p[i]]);
    return res;
}
int main(){
    scanf("%d",&n);
    Prime();
    Catalan(n).print();
    return 0;
} 

P2532 [AHOI2012]树屋阶梯

原文：https://www.cnblogs.com/yu-xing/p/11222910.html