首页 > 代码库 > bzoj2822 [AHOI2012]树屋阶梯
bzoj2822 [AHOI2012]树屋阶梯
Description
暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了个难题。由于地上露营湿气重，必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为N+1尺（N为正整数）的大树上，正当他发愁怎么爬上去的时候，发现旁边堆满了一些空心四方钢材（如图1.1），经过观察和测量，这些钢材截面的宽和高大小不一，但都是1尺的整数倍，教官命令队员们每人选取N个空心钢材来搭建一个总高度为N尺的阶梯来进入树屋，该阶梯每一步台阶的高度为1尺，宽度也为1尺。如果这些钢材有各种尺寸，且每种尺寸数量充足，那么小龙可以有多少种搭建方法？（注：为了避免夜里踏空，钢材空心的一面绝对不可以向上。）
.jpg)
以树屋高度为4尺、阶梯高度N=3尺为例，小龙一共有如图1.2所示的5种
搭 建方法：
.jpg)
Input
一个正整数 N(1≤N≤500)，表示阶梯的高度
Output
一个正整数，表示搭建方法的个数。（注：搭建方法个数可能很大。）
Sample Input
3
Sample Output
5
HINT
1 ≤N≤500
高精版卡特兰数……直接用模板的速度有点慢
#include<cstdio>#include<iostream>#define LL long long#define mx 1000using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}struct gaojing{ int len; int a[mx+10];}mult,ans,zero,one;inline void set0(gaojing &s){ s.len=1; for (int i=1;i<=mx+5;i++)s.a[i]=0;}inline void inputn(gaojing &a){ set0(a); char ch=getchar(); while (ch<‘0‘||ch>‘9‘)ch=getchar(); while (ch>=‘0‘&&ch<=‘9‘) { a.a[a.len++]=ch-‘0‘; ch=getchar(); } a.len--; int change[mx+15]; for (int i=1;i<=a.len;i++) change[i]=a.a[i]; for (int i=1;i<=a.len;i++) a.a[i]=change[a.len-i+1]; while (a.a[a.len]==0)a.len--;} inline void put(gaojing a){ for (int i=a.len;i>=1;i--)printf("%d",a.a[i]); printf("\n");}inline gaojing operator + (const gaojing &a,const gaojing &b){ gaojing c;set0(c); int maxlen=max(a.len,b.len); for (int i=1;i<=maxlen;i++) { c.a[i]=c.a[i]+a.a[i]+b.a[i]; if (c.a[i]>=10) { c.a[i+1]+=c.a[i]/10; c.a[i]%=10; } } c.len=maxlen+4; while (!c.a[c.len]&&c.len>1) c.len--; return c;}inline gaojing operator * (const gaojing &a,const gaojing &b){ gaojing c;set0(c); for(int i=1;i<=a.len;i++) for (int j=1;j<=b.len;j++) c.a[i+j-1]+=a.a[i]*b.a[j]; c.len=a.len+b.len+5; for (int i=1;i<=c.len;i++) { c.a[i+1]+=c.a[i]/10; c.a[i]%=10; } while (!c.a[c.len]&&c.len>1)c.len--; return c;}inline gaojing operator ^(const gaojing &a,int p){ gaojing ans=one,mult=a; while (p) { if (p&1)ans=ans*mult; mult=mult*mult; p>>=1; } return ans;}inline void chushihua(){ set0(zero); zero.len=1; set0(one);one.len=1;one.a[1]=1;}int n,len,now;bool mrk[1010];int prime[1010],rep[1010],mn[1010];inline void getprime(){ for (int i=2;i<=2*n;i++) { if (!mrk[i])prime[++len]=i,mn[i]=len; for (int j=1;prime[j]*i<=2*n&&j<=len;j++) { mrk[prime[j]*i]=1; mn[prime[j]*i]=j; if (i%prime[j]==0)break; } }}inline void calc(int x,int f){ while (x!=1) { rep[mn[x]]+=f; x/=prime[mn[x]]; }}int main(){ chushihua();ans=one;mult=one; n=read(); getprime(); for (int i=n+2;i<=2*n;i++)calc(i,1); for (int i=1;i<=n;i++)calc(i,-1); for (int i=2;i<=2*n;i++) { mult=mult+one; if (mrk[i])continue;else now++; if (rep[now])ans=ans*(mult^rep[now]); } put(ans);}
bzoj2822 [AHOI2012]树屋阶梯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。