Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1485: [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)。

题解

首先映入眼帘的一定是一个O(n^2)的DP
对于这个东西来讲
奇数位置的东西确定了 偶数位置的方案数就唯一了
所以我们只考虑奇数方案数
可以用dp[i][j]表示前i个位置 填到最大的数是j
用前缀和优化可以到O(n^2)
代码看hzwer那里的好了
直接上满分做法
你都想到了这里
打个表 发现是个卡特兰数列 惊不惊喜
然后变成了组合数取模这样的一种状态
F(n)=C(2*n,n)/(n+1)
发现模数p不是个质数

怎么办?显然不能上Lucas
这个时候用到一种非常实用的算法
记cnt数组表示分解质因数之后每个因数出现了多少次
然后发现cnt[prime]才有贡献
从大到小for(m->1) ,根据该数是在分母还是分子来确定它是+1还是-1(也就是代码中的add(x,-1)还是add(x,1))
if(当i为素数时){cnt[i]++;}
if(当i不为素数时){
cnt[i]++;
cnt[d[i]]+=cnt[i],cnt[i/d[i]]+=cnt[i];
//把cnt[i]的值转移到cnt[d[i]]和cnt[i/d[i]]
cnt[i]=0;
//最后记得清空cnt[i]因为cnt[i]已经转移到cnt[它的因数]去了
}
但是i/d[i]有可能不是素数,没关系,从大到小for,之后又会for到i/d[i],又可以继续分解它了。
最后只有素数i的cnt[i]!=0
讲解有点乱 上代码好了

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏