[AHOI2012]树屋阶梯 题解（卡特兰数）

[AHOI2012]树屋阶梯

Description

Solution

1.我们发现对于任何大小为i的树屋阶梯，都可以由左上角放一块大小为j的以及右下角放一块大小为(i−j−1)的树屋阶梯，再在空缺的地方由单个大块的矩形填充即可构成，那么这个构成的树屋阶梯一共有 j+(i−j−1)+1个钢材，正好是i个。

2.因为j可以在 0 到 i−1取且可以证明每一个构成的树屋阶梯一定各不相同，所以我们可以得到树屋阶梯方案与大小关系的递推式c[n]=Σ(0≤k<n)c[k]*c[n-k-1]，边界条件为c[0]=c[1]=1;

3.我们发现这就是n对应的卡特兰数，输出n对应的卡特兰数就好，因为没有要求取模，考虑使用高精度；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

int ans[100001]={},x=0;

void mul(int n){

	for(int i=1;i<=ans[0];++i){

		ans[i]=ans[i]*n+x;

		x=ans[i]/10;

		ans[i]%=10;

	}

	while(x>0){

		ans[0]++;

		ans[ans[0]]=x%10;

		x/=10;

	}

}

void div(int n){

	int q=0;

	for(int i=ans[0];i>=1;--i)

	 {

	 	x=(ans[i]+q*10)%n;

	 	ans[i]=(ans[i]+q*10)/n;

	 	q=x;

	 }

	 while(ans[ans[0]]==0)ans[0]--;

}

int main(){

	ans[0]=ans[1]=1;

	int n;

	scanf("%d",&n);

	for(int i=n+2;i<=(n<<1);++i)mul(i);

	for(int i=2;i<=n;++i) div(i);

	for(int i=ans[0];i>0;--i)printf("%d",ans[i]);

	printf("\n");

	return 0;

}

卡特兰数基础知识部分可以参考我的题解：http://www.cnblogs.com/COLIN-LIGHTNING/p/8450053.html