题目:P2532 [AHOI2012]树屋阶梯
思路:
打表之后不难看出是裸的Catalan数。简单证明一下:
对于任意一种合法方案,都可以表示为在左下角先放一个\(k*(n+1-k),k\in[1,n]\)的矩形,再在矩形的上边和右边分别放\(k-1\)阶台阶和\(n-k\)阶台阶。
例如下图(从luogu题解中盗的图...):
在左下角先放了一个\(2*3\)的矩形,之后在矩形上边放\(1\)阶台阶,在矩形右边放\(2\)阶台阶。
不难看出矩形上边和右边两部分独立,只要枚举左下矩阵长度,对每种矩形,把上边和右边的方案数相乘(乘法原理),再把不同矩形长度得到的答案相加(加法原理)就能得到总方案数。
设\(h(n)\)为n阶台阶方案数,得到递推式\(h(n)=\sum_{k=1}^nh(k-1)*h(n-k)\),就是Catalan数。
计算时分解质因数即可。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 5000,base=10000,power=4;
int n,tot,p[N],mindiv[N],cnt[N];
struct bigint{
int len,d[N];
inline bigint (){
memset(d,0,sizeof(d));
len=1;
}
inline bigint(int num){
len=1;
d[1]=num;
}
void clean(){
while(len>1&&!d[len]) --len;
}
inline bigint operator * (const bigint &b)const{
bigint c;
c.len=len+b.len;
for(int i=1;i<=len;++i) for(int j=1;j<=b.len;++j)
c.d[i+j-1]+=d[i]*b.d[j],c.d[i+j]+=c.d[i+j-1]/base,c.d[i+j-1]%=base;
c.clean();
return c;
}
inline void print(){
clean();
printf("%d",d[len]);
for(int i=len-1;i;--i) printf("%0*d",power,d[i]);
}
};
void Prime(){
for(int i=2;i<=2*n;++i){
if(!mindiv[i]) mindiv[i]=p[++tot]=i;
for(int j=1;j<=tot;++j){
if(i*p[j]>2*n||p[j]>mindiv[i]) break;
mindiv[i*p[j]]=p[j];
}
}
}
void add(int num){
while(num^1){
++cnt[mindiv[num]];
num/=mindiv[num];
}
}
void del(int num){
while(num^1){
--cnt[mindiv[num]];
num/=mindiv[num];
}
}
bigint quickpow(int a,int b){
bigint res=1,c=a;
while(b){
if(b&1) res=res*c;
c=c*c;
b>>=1;
}
return res;
}
bigint Catalan(int n){
for(int i=n+2;i<=2*n;++i) add(i);
for(int i=1;i<=n;++i) del(i);
bigint res=1;
for(int i=1;i<=tot;++i) res=res*quickpow(p[i],cnt[p[i]]);
return res;
}
int main(){
scanf("%d",&n);
Prime();
Catalan(n).print();
return 0;
}
P2532 [AHOI2012]树屋阶梯的更多相关文章
-
洛谷P2532 [AHOI2012]树屋阶梯(Catalan数)
P2532 [AHOI2012]树屋阶梯 题目描述 输入输出格式 输入格式: 一个正整数N(1<=N<=500),表示阶梯的高度. 输出格式: 一个正整数,表示搭建方法的个数.(注:搭建方 ...
-
P2532 [AHOI2012]树屋阶梯 卡特兰数
这个题是一个卡特兰数的裸题,为什么呢?因为可以通过划分来导出递推式从而判断是卡特兰数,然后直接上公式就行了.卡特兰数的公式见链接. https://www.luogu.org/problemnew/s ...
-
【题解】洛谷P2532 [AHOI2012]树屋阶梯(卡特兰数+高精)
洛谷P2532:https://www.luogu.org/problemnew/show/P2532 思路 来自Sooke大佬的推导: https://www.luogu.org/blog/Sook ...
-
Luogu P2532 [AHOI2012]树屋阶梯 卡特兰数
接着压位OvO... 我不会告诉你答案就是卡特兰数... 为什么呢? 首先,$ans[0]=1,ans[1]=1,ans[2]=2$ 对于$ans[3]$,我们可以发现他是这样来的: $ans[3]= ...
-
BZOJ 2822: [AHOI2012]树屋阶梯 [Catalan数 高精度]
2822: [AHOI2012]树屋阶梯 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 779 Solved: 453[Submit][Status] ...
-
[AHOI2012]树屋阶梯 题解(卡特兰数)
[AHOI2012]树屋阶梯 Description 暑假期间,小龙报名了一个模拟野外生存作战训练班来锻炼体魄,训练的第一个晚上,教官就给他们出了个难题.由于地上露营湿气重,必须选择在高处的树屋露营. ...
-
【BZOJ 2822】2822: [AHOI2012]树屋阶梯(卡特兰数+高精度)
2822: [AHOI2012]树屋阶梯 Description 暑假期间,小龙报名了一个模拟野外生存作战训练班来锻炼体魄,训练的第一个晚上,教官就给他们出了个难题.由于地上露营湿气重,必须选择在高处 ...
-
bzoj2822[AHOI2012]树屋阶梯(卡特兰数)
2822: [AHOI2012]树屋阶梯 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 879 Solved: 513[Submit][Status] ...
-
题解 P2532 【[AHOI2012]树屋阶梯】
本题运用卡特兰数求解. 卡特兰数有两种表达方式: 1)\(h_i=\sum^{k=0}_{i-1}h_kh_{i-k-1}\) 2)\(h_i=\frac{1}{n+1}C^{n}_{2n}\) 运用 ...
随机推荐
-
【转载】Dubbo与Zookeeper、SpringMVC整合和使用(负载均衡、容错)
http://blog.csdn.net/congcong68/article/details/41113239 互联网的发展,网站应用的规模不断扩大,常规的垂直应用架构已无法应对,分布式服务架构以及 ...
-
3款强大的BootStrap的可视化制作工具推荐
http://www.25xt.com/html5css3/7342.html 25学堂看到最近很多朋友在学习Bootstrap前端主题框架.顾让25学堂的小编给大家找来了3款适合Bootstrap初 ...
-
SVN简明使用方法 .
SVN简明使用方法 TortoiseSVN 是 Subversion 版本控制系统的一个免费开源客户端,可以超越时间的管理文件和目录.文件保存在*版本库,除了能记住文件和目录的每次修改以外,版本库非 ...
-
Query获取值常用
Query获取Select选择的Text和Value:语法解释:1. $("#select_id").change(function(){//code...}); //为Sel ...
-
javascript写贪吃蛇游戏(20行代码!)
<!doctype html> <html> <body> <canvas id="can" width="400" ...
-
MongoDB之Java测试代码(DAO层)
MongoInit.java是数据库初始化及连接类 MongoUtils.java是对mongodb的各种操作方法 MongoInit.java package com.wlwcloud.datate ...
-
python中线程的知识点
什么是线程? 程序的执行线路.每个进程默认有一条线程.线程包含了程序的具体步骤. 多线程就是一个进程中有除主线程(默认线程)外还有多个线程. 线程与进程的关系(进程包含线程,而线程依赖进程存在) 1. ...
-
BZOJ 1497 最大获利
最大权闭合子图 对于这个题,可以抽象成一个图论模型,如果我们把用户与其要求建立的中转站连边,获得的利益看成正权值,付出的代价看成负权值,我们可以发现,选取一个用户的时候,就相当于选取了一个闭合子图. ...
-
[性能调优]如何通过读PeopleSoft Trace文件来调优
理解PeopleSoft Trace文件对于解决性能问题是绝对有必要的.你可能面临一个问题,用户抱怨性能较慢,而OEM并没有补货SQL,你有2种方法选择:使用PeopleSoft trace检查或启用 ...
-
HOJ 2148&POJ 2680(DP递推,加大数运算)
Computer Transformation Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4561 Accepted: 17 ...