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;

}