「BZOJ1485」[HNOI2009] 有趣的数列 (卡特兰数列)
「BZOJ1485」[HNOI2009] 有趣的数列
Description
我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件:
(1)它是从1到2n共2n个整数的一个排列{ai};
(2)所有的奇数项满足a1<a3<…<a2n-1,所有的偶数项满足a2<a4<…<a2n;
(3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项,即:a2i-1<a2i。
现在的任务是:对于给定的n,请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod P的值。
Input
输入文件只包含用空格隔开的两个整数n和P。输入数据保证,50%的数据满足n≤1000,100%的数据满足n≤1000000且P≤1000000000。
Output
仅含一个整数,表示不同的长度为2n的有趣的数列个数mod P的值。
Sample Input
3 10
Sample Output
5
对应的5个有趣的数列分别为(1,2,3,4,5,6),(1,2,3,5,4,6),(1,3,2,4,5,6),(1,3,2,5,4,6),(1,4,2,5,3,6)。
题解
对于 A4 来说 它一定大于前三个
对于 A3 来说 它一定小于后五个
所以可以推断 AI <2*i
可以容易得到一个n^2的dp
f[i][j]表示前i位填到数字j的方案,即第i位用的是j
f[i][j]=f[i][j-1]+f[i-1][j-1] (j<=2*i-1)
f[i][j]=f[i][j-1] (j>2*i-1)
输出前几项,发现是个卡特兰数列 F(n)=C(2*n,n)/(n+1)
分解质因数求即可
至于为什么是卡特兰数列?其实就是从左往右扫每个数,把放在奇数项看作入栈,偶数看作出栈
50 分 dp
#include<bits/stdc++.h>
using namespace std;
int n,mod;
int f[][];
int main(){
scanf("%d%d",&n,&mod);
for(int i=;i<=*n;i++) f[][i]=;
for(int i=;i<=n;i++)
for(int j=;j<=*n;j++)
if (j<=*i-) f[i][j]=(f[i][j-]+f[i-][j-])%mod;
else f[i][j]=f[i][j-]%mod;
printf("%d\n",f[n][*n]);
return ;
}
100 分 卡特兰
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+;
ll pri[MAXN],mn[MAXN*],num[MAXN*],ans=;
int n,mod,cnt;
bool use[MAXN*];
void getpri(){
for (int i=;i<=*n;i++){
if (!use[i]) pri[++cnt]=i,mn[i]=cnt;
for (int j=;pri[j]*i<=*n&&j<=cnt;j++){
use[pri[j]*i]=,mn[pri[j]*i]=j;
if (i%pri[j]==) break;
}
}
}
void add(int x,int f){
while (x!=){
num[mn[x]]+=f;
x/=pri[mn[x]];
}
}
int main(){
scanf("%d%d",&n,&mod);
getpri();
for (int i=*n;i>n;i--) add(i,);
for (int i=;i<=n;i++) add(i,-);
add(n+,-);
for (int i=;i<=cnt;i++) while (num[i]--) ans=(ans*pri[i])%mod;
printf("%lld\n",ans);
return ;
}
最新文章
- c#第三方控件地址
- Octopus系列之关于多选属性如何在OO中表示呢?
- Hadoop伪分布式模式部署
- Zabbix监控之迁移zabbix server
- js匿名函数,闭包
- JS对象与原型链
- react-native-printer
- mysql5.7 datetime 默认值为‘0000-00-00 00:00:00&#39;值无法创建问题解决
- JS调用webservice服务
- Inheritance setUp() and tearDown() methods from Classsetup() and Classteardown
- java保留两位小数和js保留两位小数一致性研究
- PHPWord 打印 快递单/合同
- ArcThemALL!5.1:解压、脱壳、压缩样样精通
- Python中的常规习题
- 谷歌发布 Android 8.1 首个开发者预览版,优化内存效率
- 机器学习中的 ground truth
- 通过phoenix查看hbase中表的结构
- .NET泛型解析(上)
- //todo 的用处
- JS 错误处理与调试
热门文章
- (转)Asp.Net生命周期系列五
- (转)Asp.Net生命周期系列三
- 编写高质量代码改善C#程序的157个建议——建议50:在Dispose模式中应区别对待托管资源和非托管资源
- wpf控件开发基础
- GitHub小技巧-定义项目语言
- SharePoint 2013报错之“指定的文件不是有效的电子表格或者没有包含要导入的数据”
- TSQL--删除正在运行的数据库
- C#ADO.NET基础二
- Markdown使用心得
- 「CF 600E」 Lomsat gelral