BZOJ1485:[HNOI2009]有趣的数列(卡特兰数)
2024-10-19 14:41:13
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)。
Solution
卡特兰数。每次找最前面的奇数/偶数位置放,显然若偶数位不多于奇数位就是合法的,然后就成了卡特兰数。
我才不会说我一开始是先直接猜了个卡特兰数交上去的
Code
#include<iostream>
#include<cstdio>
#define N (2000009)
#define LL long long
using namespace std; LL n,MOD,cnt,ans=,prime[N],Keg[N],d[N]; void Euler()
{
for (int i=; i<=*n; ++i)
{
if (!d[i]){d[i]=i; prime[++cnt]=i;}
for (int j=; j<=cnt && i*prime[j]<=*n; ++j)
{
d[i*prime[j]]=prime[j];
if (i%prime[j]==) break;
}
}
} void Divide(LL x,int opt)
{
while (x!=) Keg[d[x]]+=opt,x/=d[x];
} int main()
{
scanf("%lld%lld",&n,&MOD);
Euler();
for (int i=n+; i<=*n; ++i) Divide(i,);
for (int i=; i<=n; ++i) Divide(i,-);
Divide(n+,-);
for (int i=; i<=*n; ++i)
for (int j=; j<=Keg[i]; ++j)
ans=ans*i%MOD;
printf("%lld\n",ans);
}
最新文章
- Hibernate组件和关联映射
- 关于java.lang.NoSuchMethodError: android.widget.RelativeLayout.setBackground的解决办法
- 反射动态创建不同的Processor
- 有用的dede表单代码
- Objective-C:模拟按钮点击事件理解代理模式
- 欧拉工程第70题:Totient permutation
- Verilog HDL常用的行为仿真描述语句
- spring framework 4 源码阅读(2)---从ClassPathXmlApplicationContext开始
- c# WinForm开发 DataGridView控件的各种操作总结(单元格操作,属性设置)
- 【USACO09OCT】热浪Heat Wave
- [self init]
- actionbar详解(二)
- 如何像Python高手(Pythonista)一样编程
- 2018牛客网暑假ACM多校训练赛(第五场)H subseq 树状数组
- 从零开始学 Web 之 jQuery(一)jQuery的概念,页面加载事件
- golang xorm框架的使用
- gradle ---->; 安装和使用
- pytest 单元测试
- C指针与内存
- windows10 升级1803后,远程错误提示“出现身份验证错误,要求的函数不受支持 CredSSP 加密 Oracle修正”的解决办法
热门文章
- SQL Serever学习11——数据库的安全管理
- CodeForces 604A(浮点数)
- 最大行走路线问题(DP)
- eclipse 更改背景颜色字体
- 通用CSS命名规范
- Maven学习总结(七):Maven的聚合和继承
- Maven学习总结(五):maven命令的含义及用法
- log4net.dll添加报错
- 你真的了解Fragment的生命周期吗?
- org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): cn.gaiay.business.helper.dao.LiveRegenrationRecordMapper.insert