P2532 [AHOI2012]树屋阶梯（卡特兰数）
题目描述
输入输出格式
输入格式：
一个正整数N（1<=N<=500），表示阶梯的高度。
输出格式：
一个正整数，表示搭建方法的个数。（注：搭建方法的个数可能很大）
输入输出样例
说明
40%的数据：1<=N<=20
80%的数据：1<=N<=300
100%的数据：1<=N<=500
一眼看上去以为是dp ， 然后推出来的转移方程：
dp[i+1][j] += dp[i][k] (k∈【1，i】，j∈【2，j+1】）
如果现在是3层，最左边的一列被分成了2快，那么他可以对下一层的最左边一列被分成2到3块的方案书做出贡献
然后，就wa，打了高精，就t了 qwq qwq qwq qwq qwq qwq qwq 我说：卧槽？
发现高精很慢，然后就去看题解了： 卡特兰数！！！
卧槽？ 我怎么没发现，用程序打一波，发现果然是卡特兰数：
那就简单了，直接上递推式：
根据公式 f(n)=((n+2)*(n+3)*...*(n+n))/(1*2*3*...*n);
这个式子百度一波就出来（其实这是n和m相等时候的式子
最后就是知道最后的数是一个整数，所以一定能够整出，也就说分子的所有质因子分母也有，所以提前约掉分母，
这样只写高精乘法就行了
1 #include <cstdio>
2 #include <iostream>
3 #define maxn 120005
4 #define ll long long
5 using namespace std;
6 int n,g;
7 int a,b,fm[maxn],fz[maxn],ans[maxn*100];
8
9 int qpow(int a,int b){//快速幂
10 int res=1;
11 for(;b;b>>=1){
12 if(b&1)res=res*a;
13 a*=a;
14 }
15 return res;
16 }
17
18 //ans[0]存大整数的位数
19 void mul(int x){
20 int k=0;//向前一步的进位
21 for(int i=1;i<=ans[0];i++){
22 ans[i]*=x;
23 ans[i]+=k;
24 k=ans[i]/10;
25 ans[i]%=10;
26 }
27 while(k){
28 ans[++ans[0]]+=k;
29 k=ans[ans[0]]/10;
30 ans[ans[0]]%=10;
31 }
32 }
33
34 int main(){
35 scanf("%d",&n);
36 for(int i=2;i<=n;++i){
37 a=n+i;//(n+2)*(n+3)*...*(2n) 分子
38 for(int j=2;j*j<=a;j++){//质因数分解
39 while(a%j==0)fz[j]++,a/=j;
40 }
41 if(a>1) fz[a]++;
42 b=i;//1*2*3*...*n 分母
43 for(int j=2;j*j<=b;j++){
44 while(b%j==0)fm[j]++,b/=j;
45 }
46 if(b>1) fm[b]++;
47 }
48 ans[0]=ans[1]=1;
49 for(int i=2;i<=n*2;i++){
50 if(fz[i]==0) continue;
51 fz[i]=fz[i]-fm[i];
52 if(fz[i]==0) continue;
53 int x=qpow(i,fz[i]);
54 if(x!=1) mul(x);
55 }
56 for(int i=ans[0];i>=1;--i) printf("%d",ans[i]);//注意要倒序输出
57 return 0;
58 }