题目描述
暑假期间,小龙报名了一个模拟野外生存作战训练班来锻炼体魄,训练的第一个晚上,教官就给他们出了个难题。由于地上露营湿气重,必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为N+1尺(N为正整数)的大树上,正当他发愁怎么爬上去的时候,发现旁边堆满了一些空心四方钢材(如图1.1),经过观察和测量,这些钢材截面的宽和高大小不一,但都是1尺的整数倍,教官命令队员们每人选取N个空心钢材来搭建一个总高度为N尺的阶梯来进入树屋,该阶梯每一步台阶的高度为1尺,宽度也为1尺。如果这些钢材有各种尺寸,且每种尺寸数量充足,那么小龙可以有多少种搭建方法?(注:为了避免夜里踏空,钢材空心的一面绝对不可以向上。)
以树屋高度为4尺、阶梯高度N=3尺为例,小龙一共有如图1.2所示的5种
搭 建方法:
输入
一个正整数 N(1≤N≤500),表示阶梯的高度
输出
一个正整数,表示搭建方法的个数。(注:搭建方法个数可能很大。)
样例输入
3
样例输出
5
提示
1 ≤N≤500
设f[i]表示n=i时的答案,考虑这样一种构造方法:
在n阶阶梯的左上角放一个i阶阶梯,右下角放一个n-i-1阶阶梯,剩下的部分用一个大矩形补上,这样恰好用了n个矩形
那么f[n]=f[0]*f[n-1]+f[1]*f[n-2]+……+f[n-2]*f[1]+f[n-1]*f[0]
这个就是卡特兰数的递推式!
因为没有模数,所以要高精度。
将卡特兰数用组合数的通项公式表示,枚举每个质因子在分子和分母分别出现几次,用分子的减去分母的,剩下的就是一个高精乘低精。
#include<set> #include<map> #include<queue> #include<cmath> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; struct miku { int len; int a[10010]; }; int n; miku multiply(miku x,int y) { miku z; for(int i=1;i<=x.len;i++) { z.a[i]=x.a[i]*y; } for(int i=2;i<=x.len;i++) { z.a[i]+=z.a[i-1]/10; z.a[i-1]%=10; } z.len=x.len; while(z.a[z.len]>10) { z.len++; z.a[z.len]+=z.a[z.len-1]/10; z.a[z.len-1]%=10; } return z; } miku divide(miku x,int y) { miku z; int res=0; for(int i=x.len;i>=1;i--) { res=res*10+x.a[i]; z.a[i]=res/y; res%=y; } z.len=x.len; while(z.a[z.len]==0) { z.len--; } return z; } int main() { scanf("%d",&n); miku ans; ans.len=1; ans.a[1]=1; for(int i=n+2;i<=2*n;i++) { ans=multiply(ans,i); } for(int i=1;i<=n;i++) { ans=divide(ans,i); } for(int i=ans.len;i>=1;i--) { printf("%d",ans.a[i]); } }