题意

我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：(1)它是从1到2n共2n个整数的一个排列ai；(2)所有的奇数项满足a1<a3<…<a2n−1，所有的偶数项满足a2<a4<…<a2n；n≤1000000，P≤1000000000。

分析

这么菜的题我都没有想到。。。一头撞死算了。 考虑每次都找最前的奇数位或最前的偶数位来放数字，但有第三个限制所以任意时刻偶数位不能多于奇数位，于是问题就变成了卡特兰数。 直接线性筛分解质因数即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define N 2000005 #define LL long long using namespace std; int n,p,not_PRime[N],prime[N],tot,low[N],s[N]; void get_prime(int n) { for (int i=2;i<=n;i++) { if (!not_prime[i]) { prime[++tot]=i;low[i]=i; } for (int j=1;j<=tot&&prime[j]*i<=n;j++) { not_prime[prime[j]*i]=1; low[i*prime[j]]=prime[j]; if (i%prime[j]==0) break; } } } void solve(int x,int y) { while (x>1) { s[low[x]]+=y; x/=low[x]; } } int main() { scanf("%d%d",&n,&p); get_prime(n*2); for (int i=1;i<=n;i++) solve(i,-1); for (int i=n+2;i<=n*2;i++) solve(i,1); int ans=1; for (int i=2;i<=n*2;i++) for (int j=1;j<=s[i];j++) ans=(LL)ans*i%p; printf("%d",ans); return 0; }