$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

$依次填入1,2,3,…,2n，需满足任何时候奇数项个数\ge 偶数项个数，则\ res=C_{2n}^{n}-C_{2n}^{n-1}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n,p;
int primes[N],cnt;
bool st[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int get(int n,int p)
{
    int res=0;
    while(n) res+=n/p,n/=p;
    return res;
}

int C(int a,int b)
{
    int res=1;
    for(int i=0;i<cnt;i++)
    {
        int prime=primes[i];
        int s=get(a,prime)-get(a-b,prime)-get(b,prime);
        while(s--) res=(LL)res*prime%p;
    }
    return res;
}

int main()
{
    init(N-1);

    cin>>n>>p;

    cout<<(C(2*n,n)-C(2*n,n-1)+p)%p<<endl;

    return 0;
}