[HNOI2009] 有趣的数列

题意

要统计长度为 2n 的排列，满足：

奇数位置严格递增
偶数位置严格递增
每一对相邻位置满足左边小于右边

输出这样的排列个数对 p 取模的结果。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int n;
i64 ans;
int a[25];
bool used[25];
i64 mod;

void dfs(int pos) {
    if (pos > 2 * n) {
        ans++;
        return;
    }

    for (int x = 1; x <= 2 * n; x++) {
        if (used[x]) {
            continue;
        }

        // 奇数位置要满足奇数位递增。
        if (pos >= 3 && (pos & 1) && a[pos - 2] >= x) {
            continue;
        }

        // 偶数位置要满足偶数位递增。
        if (pos >= 4 && !(pos & 1) && a[pos - 2] >= x) {
            continue;
        }

        // 每一对还要满足 a[2i-1] < a[2i]。
        if (!(pos & 1) && a[pos - 1] >= x) {
            continue;
        }

        a[pos] = x;
        used[x] = true;
        dfs(pos + 1);
        used[x] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> mod;

    dfs(1);
    cout << ans % mod << '\n';

    return 0;
}

这个暴力直接枚举排列，再检查三个条件。

关键识别是：这题的答案就是第 n 个 Catalan 数。

样例：

n = 1 时答案 1
n = 2 时答案 2
n = 3 时答案 5

完全对应 Catalan 数列。

所以答案为：

Cat(n) = C(2n,n) / (n+1)

递推公式与计数公式

本题只需要计算整数形式的 Catalan 数：

Cat(n)=\frac{\binom{2n}{n}}{n+1}=\frac{(2n)!}{n!(n+1)!}

因为模数 p 不保证是质数，所以代码实际维护每个质因子 q 的指数：

cnt_q = v_q((2n)!)-v_q(n!)-v_q((n+1)!)

但这里有一个坑：

模数 p 不一定是质数

所以不能像普通模质数题那样直接乘逆元。

正确做法

改用质因数分解来算整个整数。

对每个质数 q，计算它在：

(2n)!
n!
(n+1)!

中的指数，做差后得到它在 Catalan 数里的指数：

cnt = v_q((2n)!) - v_q(n!) - v_q((n+1)!)

最后把所有 q^cnt 乘起来，对 p 取模即可。

代码

cpp

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
75
76
77
78
79
80
81
82
83
84
85
86
87#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 1000000 + 5;

int n;
i64 mod;
int prime_cnt;
int primes[MAXN];
bool vis[MAXN];

// 线性筛出 1..limit 里的所有质数。
void get_primes(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (!vis[i]) {
            primes[++prime_cnt] = i;
        }
        for (int j = 1; j <= prime_cnt; j++) {
            int p = primes[j];
            if (1LL * p * i > limit) {
                break;
            }
            vis[p * i] = true;
            if (i % p == 0) {
                break;
            }
        }
    }
}

// 计算质数 p 在 n! 中出现了多少次。
i64 count_in_factorial(int x, int p) {
    i64 ans = 0;
    while (x > 0) {
        x /= p;
        ans += x;
    }
    return ans;
}

i64 quick_pow(i64 base, i64 exp, i64 mod) {
    i64 ans = 1 % mod;
    base %= mod;

    while (exp > 0) {
        if (exp & 1LL) {
            ans = ans * base % mod;
        }
        base = base * base % mod;
        exp >>= 1LL;
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> mod;

    if (mod == 1) {
        cout << 0 << '\n';
        return 0;
    }

    get_primes(2 * n);

    // Catalan(n) = C(2n, n) / (n + 1)
    // 用质因数分解来做，避免模数不一定是质数时不能直接求逆元。
    i64 ans = 1 % mod;
    for (int i = 1; i <= prime_cnt; i++) {
        int p = primes[i];
        i64 cnt = count_in_factorial(2 * n, p)
                - count_in_factorial(n, p)
                - count_in_factorial(n + 1, p);
        if (cnt > 0) {
            ans = ans * quick_pow(p, cnt, mod) % mod;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

线性筛 $O(n)$
统计所有质数指数总体也是线性级别
空间复杂度 $O(n)$

总结

这题表面是排列计数，实质是 Catalan 数。

真正的难点不在识别模型，而在处理“模数不一定是质数”这个限制。
一旦改成质因数分解，整个问题就重新变成了一个稳定可做的组合数计算题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。