bzoj 2822 [AHOI2012]树屋阶梯 卡特兰数

本文主要是介绍bzoj 2822 [AHOI2012]树屋阶梯 卡特兰数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为规定n层的阶梯只能用n块木板
那么就需要考虑，多出来的一块木板往哪里放
考虑往直角处放置新的木板
不管怎样，只有多的木板一直扩展到斜边表面，才会是合法的新状态，发现，这样之后，整个n层阶梯就被分成了i层和n-1-i层的阶梯，即

$$f(n)=\sum_{i=0}^{n-1}{f(i)\times f(n-1-i)}$$
就是卡特兰数！！！，需要高精。。差评。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1050
using namespace std;
int n,prime[N],tot,id[N],num[N];
bool bo[N];
struct bignum{int len,a[500];bignum(){len=0;memset(a,0,sizeof a);}bignum operator = (int x){while(x){a[++len]=x%10;x/=10;}return *this;}bignum operator * (int x){bignum b; b.len=len;for(int i=1;i<=len;i++){b.a[i]+=a[i]*x;b.a[i+1]+=b.a[i]/10;b.a[i]%=10;}while(b.a[b.len+1]){b.len++;b.a[b.len+1]=b.a[b.len]/10;b.a[b.len]%=10;}return b;}
}ans;
void print(bignum b){for(int i=b.len;i;i--){printf("%d",b.a[i]);}printf("\n");
}
void getprime(){for(int i=2;i<=2*n;i++){if(!bo[i]){prime[++tot]=i;id[i]=tot;}for(int j=1;j<=tot&&i*prime[j]<=2*n;j++){bo[i*prime[j]]=1; id[i*prime[j]]=j;if(i%prime[j]==0)break;}}
}
void add(int x,int y){while(x!=1){num[id[x]]+=y;x/=prime[id[x]];}
}
int main(){scanf("%d",&n);getprime();for(int i=n+2;i<=2*n;i++)add(i,1);for(int i=1;i<=n;i++)add(i,-1);ans=1;for(int i=1;i<=tot;i++)while(num[i]--) ans=ans*prime[i];print(ans);return 0;
}

这篇关于bzoj 2822 [AHOI2012]树屋阶梯 卡特兰数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---