小猫 - 题目列表

题意

圆上有 $2n$ 只小猫，要把它们两两连线，并要求所有绳子都不能交叉。

问这样的配对方案一共有多少种，答案对 $10^9+7$ 取模。

思路

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

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

using i64 = long long;

int n;
i64 memo[35][35];
bool vis[35][35];

// dfs(l, r) 表示区间 [l, r] 里的点按顺序排成一段时，
// 不相交配对的方案数。
i64 dfs(int l, int r) {
    if (l > r) {
        return 1;
    }

    if (vis[l][r]) {
        return memo[l][r];
    }
    vis[l][r] = true;

    i64 ans = 0;

    for (int k = l + 1; k <= r; k += 2) {
        ans += dfs(l + 1, k - 1) * dfs(k + 1, r);
    }

    memo[l][r] = ans;
    return ans;
}

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

    cin >> n;
    cout << dfs(1, 2 * n) << '\n';

    return 0;
}

这个暴力固定区间最左边的点，枚举它和谁配对，然后递归处理左右两段。

于是自然得到标准的 Catalan 递推：

$f[i] = \sum_{j=0}^{i-1} f[j] \cdot f[i-1-j]$

其中 $f[i]$ 表示 $i$ 对点的不相交配对方案数。

但本题 $n \leqslant 10^5$ ，直接做这个递推是 $O(n^2)$ ，过不去。

关键是继续利用 Catalan 数的等价公式：

$C_n = C_{n-1} \cdot (4n-2) / (n+1)$

模数 $10^9+7$ 是质数，所以除法可以改成乘逆元。

状态表

状态	含义
$f[i]$	$i$ 对点的不相交配对方案数
$inv[i]$	$i$ 在模 $10^9+7$ 下的逆元

于是递推写成：

$f[i] = f[i-1] \cdot (4i-2) \bmod \text{MOD} \cdot inv[i+1] \bmod \text{MOD}$

初值：

$f[0] = 1$

答案：

$f[n]$

代码

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

using i64 = long long;

const int MAXN = 100000 + 5;
const i64 MOD = 1000000007LL;

int n;
i64 inv[MAXN];
i64 f[MAXN];

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

    cin >> n;

    inv[1] = 1;
    for (int i = 2; i <= n + 1; i++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }

    f[0] = 1;

    // Catalan 递推公式：
    // C_n = C_{n-1} * (4n-2) / (n+1)
    // 在模意义下，除法改成乘逆元。
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * (4LL * i - 2) % MOD;
        f[i] = f[i] * inv[i + 1] % MOD;
    }

    cout << f[n] << '\n';

    return 0;
}

复杂度

线性求逆元 $O(n)$
线性递推答案 $O(n)$
总时间复杂度 $O(n)$
空间复杂度 $O(n)$

总结

这题和圆上不相交连线的很多题一样，本质都是 Catalan 数。

区别只在于数据范围很大，所以不能停留在区间划分的 $O(n^2)$ 递推，而要继续把它化成只依赖前一项的线性公式。

一图流解析

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

小猫

目录

题意

思路

状态表

代码

复杂度

总结

一图流解析