呜呜呜，本蒟蒻第一次做卡特兰数，实在是太菜了。写一个题解加深记忆。
Solution
首先，题里面说明 (a_2<a_4< cdots <a_{2n}) 和 (a_{2i-1}<a_{2i}) ，可得偶数位上的数比它前面任意一个数都要大。
那么我们可以将题意转化为：将 (1) ~ (2n) 放入这个数列，每次放的数要么放在最前面的奇数位要么放在最前面的偶数位。
你觉得我说的可能是废话
现在说另一个结论：一个数列填入偶数位的个数要时刻不超过填入奇数位的个数
证明：设放在了偶数位上 (a) 个数，放在奇数位上 (b) 个数，并且 (a>b) ，那么现在放了 (a+b) 个数，显然 (a>frac x2=frac {a+b}2) ，并且现在最后一个偶数位的下标是 (2 imes a) ，但是 (2 imes a>x) ，也就是说不管你在这一位放啥都是不满足条件的。
现在答案就是满足任意位偶位数不超过奇位数的数列个数
设 (f_{i,j}) 表示填了 (i) 个偶数位， (j) 个奇数位的方案数。递推方程就是 (f_{i,j}=f_{i-1,j}+f_{i,j-1})
最后的答案就是 (f_{n,n})
完结撒花
嘿嘿嘿，如果你算了一下复杂度的话，会发现递推的复杂度是 (O(n^2)) ，显然会T。
上面那个东西，和卡特兰数有很大的关系。其实就是求卡特兰数 (f_n)
所以我们要说关于卡特兰数的几个不一样的公式：
- (f_n=sumlimits_{i=0}^{n-1}f_icdot f_{n-i-1}) 这个也是递推的，复杂度依旧不对。
- (f_{n}=f_{n-1}cdot frac {4n-2}{n+1}) ，如果 (p) 是质数可以直接使用，也就是这个题。但是这个题没有保证，是做不了了的。
- (f_n=frac {C_{2n}^n}{n+1}) ，这个是可以的。
为什么这个就是可以的？因为 (f_n=frac {C_{2n}^n}{n+1}=frac {2n imes (2n-1) imes cdots imes (n+2)}{n!}) ，而一个数又可以表示成 (prod p_i^{k_i}) ，所以我们可以将每个数做质因数分解，统计每个质因子的指数即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
int min_p[N],p[N],cnt[N],tot,mod,n;
inline int fpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
inline void init(int n){
for(int i=2;i<=n;i++){
if(!min_p[i]) p[++tot]=i,min_p[i]=i;
for(int j=1;j<=tot&&p[j]*i<=n;j++){
min_p[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
int main(){
scanf("%d%d",&n,&mod);
init(2*n);
for(int i=1;i<=n;i++) cnt[i]=-1;
for(int i=n+2;i<=2*n;i++) cnt[i]=1;
for(int i=2*n;i>1;i--)
if(min_p[i]<i) cnt[min_p[i]]+=cnt[i],cnt[i/min_p[i]]+=cnt[i];
int ans=1;
for(int i=2;i<=2*n;i++)
if(min_p[i]==i) ans=(ll)ans*fpow(i,cnt[i])%mod;
printf("%lld
",ans);
}