分析

• 我们要有这种直觉：一旦发现输入是3，输出是5，很可能就是卡特兰数。关于卡特兰数的讲解可以参考：网址。

• 如何判断某个问题是不是卡特兰数呢？一般由两种方式：

（1）能得到公式：$h(n) = \sum _{i=1}^{n} h(i-1) \times h(n-i) \quad \quad h(0)=1$；

（2）能挖掘出如下性质：任意前缀中，某种东西的数量 $\ge$ 另一种东西数量。

• 从1到2n依次考察每个元素放置的位置，1只能放在第一个位置，2只能放在第二个位置，且任意时刻我们放置的数据中奇数项的个数必须大于等于偶数项的数量。否则，假设我们偶数项放置2个元素，奇数项放置3个元素，则不合法，如下图：

• 我们可以这样对应：在从1到2n依次考察每个元素时，如果这个数据放到奇数位置，标为0，否则标为1。则任意前缀中0的个数要大于等于1的个数。

• 卡特兰数为：

$$ \frac{C_{2n} ^ n}{n+1} $$

• 因为这里的p不一定是质数，其他数与p不一定存在逆元，因此不能使用求逆元的方法。因此这里使用卡特兰数推导的前一步公式：

$$ C_{2n}^{n} - C_{2n}^{n-1} $$

组合数等于三个阶乘相乘除，因此我们求出各个阶乘的质因数分解，就能得到组合数的模p后大小。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n, p;  // 这里的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] * i <= n; j++) {
            st[i * primes[j]] = 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 qmi(int a, int k) {

    int res = 1 % p;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a %p;
        k >>= 1;
    }
    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(b, prime) - get(a - b, prime);
        res = (LL)res * qmi(prime, s) % p;
    }
    return res;
}

int main() {

    cin >> n >> p;

    init(n * 2);

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

    return 0;
}