P2532 [AHOI2012]树屋阶梯
2024-09-06 14:19:53
题目: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;
}
最新文章
- 1.3---字符串重新排列后是否能够变成另一个字符串(CC150)
- 深入理解java虚拟机【内存溢出实例】
- Linux中记录终端(Terminal)输出到文本文件(转载)
- scala学习笔记(4):占位符
- 网易云课堂_程序设计入门-C语言_第四周:循环控制_2念整数
- EassyMock实践 捕获参数
- 利用H5新特性判断文件大小
- Shiro【授权过滤器、与ehcache整合、验证码、记住我】
- 机器翻译评价指标 — BLEU算法
- 从Node到Go的心路之旅
- Jmeter学习过程中遇到的那些坑
- js中变量名加“-” new Vue()不执行
- ab压力测试工具的简单使用
- 使用jackson美化输出json/xml
- EXCEL2007出错了无法使用文档中的ActiveX 控件
- 如何生成安全的密码 Hash:MD5, SHA, PBKDF2, BCrypt 示例
- Jenkins+git
- 《剑指offer》第三十一题(栈的压入、弹出序列)
- LeetCode135:Candy
- Trie树子节点快速获取法
热门文章
- vue的事件绑定
- LintCode刷题笔记-- PaintHouse 1&;2
- idea目录结构子目录在父目录后面跟着改成树形结构
- IO流10 --- 缓冲流(字节型)实现非文本文件的复制 --- 技术搬运工(尚硅谷)
- 学习线程池源码--ScheduledThreadPoolExecutor
- TYVJ4239 [NOIP2015提高组DayT3]斗地主
- python中bisect模块的使用
- 微信小程序开发之图片等比例缩放 获取屏幕尺寸图片尺寸 自适应
- React高阶组件 和 Render Props
- iOS音频篇:使用AVPlayer播放网络音乐