鸡蛋饼

题意

输入一个 N，表示圆上有 2N 个不同的点。

现在要用 N 条线段把它们两两连接起来，并要求：

每个点恰好连一次
所有线段互不相交

求这样的方案数，对 10^8+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
41
42#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;

    // 固定最左端点 l，枚举它和哪个点配对。
    // 配对后，区间会被拆成 [l+1, k-1] 和 [k+1, r] 两段。
    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;
}

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

正式做法的关键观察是：固定一个基准点，比如 1 号点。

它和某个点连线之后，这条线会把整个圆切成左右两个部分。由于线段不能相交，所以：

左边部分只能在左边内部继续配对
右边部分只能在右边内部继续配对

这两个子问题完全独立。

递推表的含义

状态	含义
`f[i]`	`i` 对点的不相交配对方案数
`j`	左边子问题分到的点对数
`i-1-j`	右边子问题分到的点对数

所以递推就是：

f[i] += f[j] * f[i-1-j]

其中 j 从 0 到 i-1 全部枚举。

这正是最经典的 Catalan 数递推。

初值：

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

using i64 = long long;

const i64 MOD = 100000007LL;

int n;
i64 f[5005];

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

    cin >> n;

    f[0] = 1;

    // Catalan 递推：
    // 任选与 1 号点配对的点，把圆分成左右两部分。
    // 如果左边有 i 对点，右边就有 n-1-i 对点。
    for (int i = 1; i <= n; i++) {
        f[i] = 0;
        for (int j = 0; j <= i - 1; j++) {
            f[i] = (f[i] + f[j] * f[i - 1 - j]) % MOD;
        }
    }

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

    return 0;
}

复杂度

双重循环递推，时间复杂度 $O(N^2)$
只用一个一维数组，空间复杂度 $O(N)$

总结

这题的本质不是“圆”本身，而是：

固定一个点后
它的连线把整体拆成两个互不干扰的子结构

一旦识别出这个拆分方式，就自然落到了 Catalan 数模型上。

目录

题意

思路

递推表的含义

代码

复杂度

总结