形式化题目

求包含 $1 \sim 2n$ 的大小为 $2n$ 的排列 $\{a_i\}$ 的数量，使得：

1. 奇数项单调递增：$a_1 < a_3 < \dots < a_{2n-1}$；
2. 偶数项单调递增：$a_2 < a_4 < \dots < a_{2n}$；
3. 相邻奇偶对满足奇数项小于偶数项：$\forall 1 \leqslant i \leqslant n,\; a_{2i-1} < a_{2i}$。

结果对给定的整数 $P$（$2 \leqslant P \leqslant 10^9$）取模。

正解

思路

1. 模型转化：卡特兰数

考虑从小到大依次将整数 $1, 2, \dots, 2n$ 填入数列中：

• 集合 $A$ 存放所有奇数项 $\{a_1, a_3, \dots, a_{2n-1}\}$，共 $n$ 个数；
• 集合 $B$ 存放所有偶数项 $\{a_2, a_4, \dots, a_{2n}\}$，共 $n$ 个数。

由于要求 $a_1 < a_3 < \dots < a_{2n-1}$ 且 $a_2 < a_4 < \dots < a_{2n}$，一旦确定哪些数字进入 $A$、哪些数字进入 $B$，它们在各自集合中的下标便唯一确定（较小的数排在前面）。

再看条件 $a_{2i-1} < a_{2i}$：对于任意前 $k$ 个填入的数字（$k = 1, 2, \dots, 2n$），设当前放入 $A$ 的数字个数为 $cnt_A$，放入 $B$ 的数字个数为 $cnt_B$。 若在某一时刻出现 $cnt_A < cnt_B$（例如 $cnt_B = m$ 且 $cnt_A < m$），这意味着偶数项 $a_{2m}$ 已经确定了填入的数值，但与其配对的奇数项 $a_{2m-1}$ 还未被填入（即后面填入的数更大），必然导致 $a_{2m-1} > a_{2m}$，与条件矛盾。

因此，在构造过程的任意前缀时刻，必须恒满足：

把「数字放入 $A$」视作左括号（或入栈），「数字放入 $B$」视作右括号（或出栈），这一约束完全等价于长为 $2n$ 的合法括号匹配序列。方案数即为经典的第 $n$ 项卡特兰数（Catalan Number）：

2. 处理任意模数的质因数分解法

本题中模数 $P$ 是任意正整数，不保证为质数，无法直接使用费马小定理求逆元。

为此，对公式 $C_n = \frac{(2n)!}{n!(n+1)!}$ 进行质因数分解：

1. 筛出 $2n$ 以内的所有质数 $p$。
2. 利用勒让德公式（Legendre’s formula）计算 $x!$ 中质因数 $p$ 的指数：
   $$E_p(x) = \sum_{k=1}^{\infty} \left\lfloor \frac{x}{p^k} \right\rfloor$$
3. 在 $C_n$ 中，质因数 $p$ 的净指数为：
   $$c_p = E_p(2n) - E_p(n) - E_p(n+1)$$
   因为 $C_n$ 为整数，必然有 $c_p \geqslant 0$。
4. 最终答案直接使用快速幂在模 $P$ 下连乘：
   $$C_n \bmod P = \left( \prod_{p \leqslant 2n} p^{c_p} \right) \bmod P$$

flowchart LR
    A[从小到大放入 1 到 2n] --> B{放入奇数项还是偶数项?}
    B -->|放入奇数项 cnt_A| C[类似入栈 / 左括号]
    B -->|放入偶数项 cnt_B| D[类似出栈 / 右括号]
    C & D --> E[任意前缀满足 cnt_A >= cnt_B]
    E --> F[模型等价于卡特兰数 C_n]
    F --> G[模数任意: 质因数分解分解阶乘]
    G --> H[勒让德公式求质数重数并模 P 累乘]

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-19 10:00
# update_at: 2026-04-19 10:00

import sys


def sieve_primes(limit: int) -> list[int]:
    """线性切片筛法产出 limit 以内的全部质数。"""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            is_prime[i * i : limit + 1 : i] = b"\x00" * len(range(i * i, limit + 1, i))
    return [i for i, p in enumerate(is_prime) if p]


def legendre_factor_count(limit: int, p: int) -> int:
    """勒让德公式计算 limit! 中质因子 p 的重数。"""
    cnt = 0
    while limit:
        cnt += limit // p
        limit //= p
    return cnt


def catalan_mod(n: int, mod: int) -> int:
    """质因数分解计算第 n 项卡特兰数 C(2n, n) / (n + 1) 对 mod 取模。"""
    primes = sieve_primes(2 * n)
    ans = 1
    for p in primes:
        exp = (
            legendre_factor_count(2 * n, p)
            - legendre_factor_count(n, p)
            - legendre_factor_count(n + 1, p)
        )
        if exp:
            ans = ans * pow(p, exp, mod) % mod
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:  # 空输入：沿用原来的 if not tokens 守卫
        return
    mod = next(data)  # 模数 P
    print(catalan_mod(n, mod))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:04
 * update_at: 2026-10-06 01:04
 */

// 有趣的数列：答案为第 n 项卡特兰数 C_n = (2n)! / (n! * (n+1)!)。
// 模数 P 是任意整数（不保证是质数），不能求逆元，
// 所以对每个质数 p 用勒让德公式算出 C_n 中 p 的指数，再用快速幂模 P 连乘。

#include <cstdio>

typedef long long ll;

const int MAXN = 2000005; // 需要 2n 以内的数，n <= 1e6

int n;
ll P;

bool is_composite[MAXN]; // is_composite[i] = true 表示 i 是合数
int primes[MAXN / 10];   // 存 2n 以内的全部质数，约 2e6/ln(2e6) 个，够用
int prime_cnt = 0;

// 线性筛：筛出 2n 以内的全部质数
void sieve(ll limit) {
    for (ll i = 2; i <= limit; ++i) {
        if (!is_composite[i]) primes[prime_cnt++] = i;
        for (int j = 0; j < prime_cnt; ++j) {
            ll nxt = (ll)primes[j] * i;
            if (nxt > limit) break;
            is_composite[nxt] = true;
            if (i % primes[j] == 0) break; // primes[j] 是 i 的最小质因子，避免重复筛
        }
    }
}

// 勒让德公式：计算 x! 中质因子 p 的指数
ll legendre(ll x, ll p) {
    ll cnt = 0;
    while (x > 0) {
        cnt += x / p;
        x /= p;
    }
    return cnt;
}

// 快速幂：p^e mod P
ll qpow(ll p, ll e) {
    ll res = 1;
    ll base = p % P;
    while (e > 0) {
        if (e & 1) res = res * base % P;
        base = base * base % P;
        e >>= 1;
    }
    return res;
}

int main() {
    scanf("%d %lld", &n, &P);
    ll m = 2LL * n;
    sieve(m);
    ll ans = 1;
    // 对每个质数 p，C_n 中 p 的净指数 = E(2n) - E(n) - E(n+1)，必然非负
    for (int i = 0; i < prime_cnt; ++i) {
        ll p = primes[i];
        ll exp = legendre(m, p) - legendre(n, p) - legendre(n + 1, p);
        if (exp > 0) ans = ans * qpow(p, exp) % P;
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

• 时间复杂度：$\mathcal{O}(n)$。
  • 筛出 $2n$ 内质数需 $\mathcal{O}(n)$；
  • 对每个质数 $p$ 计算勒让德公式耗时 $\mathcal{O}(\log_p n)$，总耗时为 $\sum_{p \leqslant 2n} \log_p(2n) = \mathcal{O}(n)$；
  • 快速幂累乘质数因子的时间为 $\mathcal{O}\left(\frac{n}{\ln n} \log P\right)$；
  • 总体在 $10^6$ 级别下运行耗时不足 0.1s。
• 空间复杂度：$\mathcal{O}(n)$。筛法标记数组和质数列表占用空间约为数兆字节，远低于 128MB 限制。

总结

本题的关键在于通过「按数值大小逐步填入」的动态视角，将排列的递增条件与奇偶约束转化成「前缀中放入奇数项的元素数量必须不小于偶数项」，建立起与出入栈序列及卡特兰数的双射模型。对于不保证模数为质数的组合计数问题，先质因数分解再模下连乘是避免除法与逆元不可用时的通用方法。