卡特兰数 - HNOI 2009 有趣的数列 - 洛谷 P3200_综合

卡特兰数 - HNOI 2009 有趣的数列 - 洛谷 P3200

$我们称一个长度为 2n 的数列是有趣的，当且仅当该数列满足以下三个条件：$

$它是从 1 到 2n 共 2n 个整数的一个排列 {a_i}；$
$所有的奇数项满足 a_1<a_3<?<a_{2n?1} ，所有的偶数项满足 a_2<a_4<?<a_{2n}；$
$任意相邻的两项 a_{2i?1} 与 a_{2i }(1≤i≤n) 满足奇数项小于偶数项，即：a_{2i?1}<a_{2i}。$

$任务是：对于给定的 n，请求出有多少个不同的长度为 2n 的有趣的数列。$

$因为最后的答案可能很大，所以只要求输出答案 mod\ P 的值。$

输入格式

只包含用空格隔开的两个整数 n 和 P。

输出格式

仅含一个整数，表示不同的长度为 2n 的有趣的数列个数 mod P 的值。

数据范围

$1≤n≤10^6, 2≤P≤10^9$

输入样例：

3 10

输出样例：

样例解释

对应的 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}。

分析：

$本题序列数量为2n，n=3时输出5=C_{6}^{3}-C_{6}^{2}，暗示本题与卡特兰数相关。$

$卡特兰数问题的一般形式：\begin{cases}①、递推式：f(n)=f(1)·f(n-1)+f(2)·f(n-2)+...(求二叉树的个数)\\\\②、性质：任意前缀中，A的数量≥B的数量。\end{cases}$

如：组合数学 -卡特兰数 - 满足条件的01序列

$题中要求0的个数≥1的个数，对应到坐标轴上，设x为0的个数，y为1的个数，需满足x≥y。$

本题中：

$我们需要确定哪些数是奇数项，哪些数是偶数项，再分别将奇数项偶数项排序，就能够确定一种方案。$

$现在从：1，2，3，...，2n中，从前到后依次确定每个数属于奇数项还是偶数项，$

$我们需要保证，任意一种方案的前缀中，奇数项的个数不能够小于偶数项的个数。$

原因：

$假设某个前缀的奇数项个数为k_1，偶数项个数为k_2，且k_1<k_2，$

$k_1<k_2，即前k_1+k_2个数中，偶数项的个数更多，说明偶数项的最后一项之前，必有奇数项还未确定，$

$因为我们是从小到大选择各个位置上的数的，那么未确定的奇数项将填入更大的数，$

$这将不满足条件：任意相邻的两项 a_{2i?1} 与 a_{2i }(1≤i≤n) 满足奇数项小于偶数项。$

举例：

$假设有2项奇数项已确定：a_1=1，a_3=3。$

$3项偶数项已确定：a_2=2，a_4=4，a_6=5，$

$那么a_5的值必大于5，即a_5>a_6，不满足条件。$

$因此，本题中的重要性质：$ 任意前缀的奇数项个数 ≥ 偶数项个数。

$我们把每一个奇数项当作一个0，偶数项当作一个1，那么问题就转化为《满足条件的01序列》这道题。$

$P不确定为质数，所以本题不方便求逆元，故用卡特兰数差的形式来求解：C_{2n}^n-C_{2n}^{n-1}。$

$通过定义，分解阶乘质因数+快速幂来求组合数。$

代码：

#include<iostream>#define ll long longusing namespace std;const int N=2e6+10;int n,mod;
int primes[N],cnt;
bool st[N];void get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]*i<=n;j++){st[primes[j]*i]=true;if(i%primes[j]==0) break;}}
}int get(int n,int p)
{int s=0;while(n) s+=n/p, n/=p;return s;
}int quick_pow(int a,int b,int mod)
{int res=1;while(b){if(b&1) res=(ll)res*a%mod;a=(ll)a*a%mod;b>>=1;}return res;
}int C(int n,int m)
{int res=1;for(int i=0;i<cnt;i++){int p=primes[i];int s=get(n,p)-get(m,p)-get(n-m,p);res=((ll)res*quick_pow(p,s,mod))%mod;}return res;
}int main()
{cin>>n>>mod;get_prime(2*n);cout<<(C(2*n,n)-C(2*n,n-1)+mod)%mod<<endl;return 0;
}