有趣的数列

题目连接：

https://www.acwing.com/problem/content/1318/

Description

我们称一个长度为 2n 的数列是有趣的，当且仅当该数列满足以下三个条件：
1.它是从 1 到 2n 共 2n 个整数的一个排列 ({ai})；
2.所有的奇数项满足 (a_1<a_3<⋯<a_{2n−1}) ，所有的偶数项满足 (a_2<a_4<⋯<a_{2n})；
3.任意相邻的两项 (a_{2i−1}) 与 (a_{2i}(1≤i≤n)) 满足奇数项小于偶数项，即：(a_{2i−1}<a_{2i})。
任务是：对于给定的 n，请求出有多少个不同的长度为 2n 的有趣的数列。
因为最后的答案可能很大，所以只要求输出答案 modP 的值。

Input

只包含用空格隔开的两个整数 n 和 P。
(1≤n≤10^6,)
(2≤P≤10^9)

Output

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

Sample Input

3 10

Sample Output

5

Hint

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

题解：

我们构造出一个奇数项和一个偶数项序列序列，最后两个序列分别排序，放在对应位置，可以构造出的数量就是答案。我们从1~2n开始依次选，任何时候奇数项选的数量一定要大于等于偶数项选的数量。所以直接求卡特兰数即刻C(2n,n)-C(2n,n-1)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
typedef long long LL;
int st[N],primes[N],tot,n,p,sum[N];
void get_primes(){
    for(int i=2;i<N;++i){
        if(!st[i]) primes[++tot]=i;
        for(int j=1;primes[j]*i<N;++j){
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;
        }
    }
}
int get(int a,int b){
    int s=0;
    while(a) s+=a/b,a/=b;
    return s;
}
LL qmi(int a,int b){
    int res=1;
    while(b) {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}
LL C(int a,int b){
    for(int i=1;i<=tot;++i){
        int prime=primes[i];
        sum[i]=get(a,prime)-get(b,prime)-get(a-b,prime);
    }
    LL res=1;
    for(int i=1;i<=tot;++i){
        res=(res*qmi(primes[i],sum[i]))%p;
    }
    return res;
}
int main(){
    cin>>n>>p;
    get_primes();
    cout<<(C(2*n,n)-C(2*n,n-1)+p)%p<<endl;
    return 0;
}