我们称一个长度为 2n 的数列是有趣的,当且仅当该数列满足以下三个条件:
它是从 1 到 2n 共 2n 个整数的一个排列 {ai};
所有的奇数项满足 a1<a3<⋯<a2n−1,所有的偶数项满足 a2<a4<⋯<a2n,任意相邻的两项 a2i−1 与 a2i 1≤i≤n) 满足奇数项小于偶数项,即:a2i−1<a2i。
任务是:对于给定的 n,请求出有多少个不同的长度为 2n 的有趣的数列。
因为最后的答案可能很大,所以只要求输出答案 modP 的值。
/*由墨染空大佬的启发,完善详细一下大佬的思路
先分析序列
第一个性质:首先奇数位置偶数位置都是递增的,如果我们从1—2n中按从小到大顺序放到相应位置
那么必然要把当前数x要放到最小的没放到的奇数位置j1或者偶数位置o1。
假如我们不这么做,因为是从1到2n依次取
所以必定导致后面的某一个数x2放在了,o1或者j1,这样x2>x1但是x2对应的位置却比x1要小,矛盾
所以必须要放到没放的最小的奇数位置或者偶数位置
第二个性质:我们必须确保当前已经放置的奇数位置个数>=偶数位置个数。如果奇位置个数<偶位置个数,则由于是1到2n
从小到大依次取出,假设偶数位置的数是x位置是y,那么之后放的数x2>x,却放在了y-1这个位置,与题意矛盾
综上用卡特兰数便可解决。*/
#include<iostream>
using namespace std;
int n,p1,cnt=0;
int st[2000100],p[2000100];//注意是两倍n
void getp()
{for(int i=2;i<=2*n;i++)
{if(!st[i])
{p[++cnt]=i;
st[i]=1;}
for(int j=1;j<=cnt&&i<=2*n/p[j];j++)
{
st[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
int get(int x,int y)
{int res=0;
while(x)
{res+=x/y;
x=x/y;
}
return res;
}
int qmi(int a,int b)
{
int res=1;
int x=a;
while(b)
{
if(b&1)
{
res=(long long)res*x%p1;
}
b>>=1;
x=(long long)x*x%p1;
}
return res;
}
int C(int a,int b)
{int res=1;
for(int k=1;k<=cnt;k++)
{int t=get(a,p[k])-get(a-b,p[k])-get(b,p[k]);
if(t)
res=(long long)res*qmi(p[k],t)%p1;
}
return res;
}
int main()
{
cin>>n>>p1;
getp();
cout<<((C(2*n,n)-C(2*n,n-1))+p1)%p1;
}