圆上的连线：从几何模型到卡特兰数计数

洛谷题号 P10413题目名“圆上的连线”出处是蓝桥杯 2023 年国赛 A 组。我第一次看到这道题时的第一反应是题面也太短了。没有大段的输入输出示例没有复杂的数据结构背景从头到尾就是“圆上有若干个点把它们连成互不相交的弦问方案数”。这种题在决赛场上反而是最考验人的——因为它把“你平时有没有把几何模型拉直成计数模型”这件事直接摆在了台面上。这篇题解我想从题面转译开始讲把卡特兰数的来龙去脉、三种推导路径、取模实现和变体迁移都捋一遍适合正在备赛蓝桥杯国赛、省赛的选手也适合所有想搞懂“圆上非交叉配对”到底在计什么的同学。1. 题面转译把圆砍一刀变成序列1.1 弦相交到底由什么决定圆是高度对称的几何对象做题时不要把坐标和角度带进来真正有用的只有点之间的相对顺序。把圆上的点按顺时针从 1 到 2n 编号任取两条弦 (a,b) 和 (c,d)它们相交的充要条件是四个端点在圆环上交错排列也就是出现 acbd 或 cadb 这种模式。反过来如果四个端点分成两段连续弧两条弦就不相交。这句话是整个问题的翻译官。因为一旦把“弦是否相交”变成“端点顺序是否交错”原来的圆就从几何对象退化成了一条带顺序的序列所有的计数都可以在一维逻辑下进行。我平时做竞赛题有个习惯看到圆、环、循环队列这类名词第一件事就是想能不能砍一刀换成链。这道题完全可以因为我们可以固定 1 号点作为序列的起点然后逆时针把剩下的点拉成一条直线。1.2 1 号点只能连偶数点固定 1 号点以后设它连向点 k。弦 (1,k) 把圆分成两段弧一段是 2 到 k-1长度为 k-2一段是 k1 到 2n长度为 2n-k。注意这两段内部的点只能互相配对任何跨越这条弦的配对都会和 (1,k) 相交所以两段弧内部的点数都必须能被 2 整除。于是 k-2 是偶数k 也得是偶数另一侧 2n-k 是偶数还是同样的结论。这个“1 号点只能连向偶数号点”的观察看似简单却是整道题的突破口。很多题解喜欢直接把递推式写出来跳过了这一步的说明导致读者只记住了式子没搞懂来历。实际上你只要自己画一个 6 个点的圆试一下 1 连 3 的情况马上就会看到两边各剩下 1 个点根本没法配对不画图推一遍也能得到同样的奇偶性结论。这道题的所有后续推导都建立在这个小小的观察上。2. 为什么答案落在卡特兰数上2.1 递推的自然诞生有了上面的剖分结构设 f[n] 表示 2n 个点能做多少种互不相交的配对方案。固定 1 号点它只能连向某个偶数号 2i其中 i 从 1 取到 n。左边一段弧里有 2i-2 个点也就是 i-1 对右边一段弧里有 2n-2i 个点也就是 n-i 对。左右两边各自独立所以f[n] Σ_{i1}^{n} f[i-1] × f[n-i]边界 f[0]1。你把这个递推式子和卡特兰数的标准递推 C_n Σ_{i1}^{n} C_{i-1} × C_{n-i} 对照一下会发现完全一样。所以答案是第 n 个卡特兰数这一点已经不需要再怀疑。卡特兰数的闭式公式可以直接写成C_n C(2n, n) / (n1)。这是本题最终的落点。到这里算法题其实已经解完了剩下的工作是如何把这个闭式高效、正确地算出来。2.2 和括号序列、出栈序列为什么是同一个模型熟悉组合计数的朋友都知道卡特兰数有几十种等价的定义场景。这里列一个最常用的表场景计数对象圆上 2n 个点的非交叉配对第 n 个卡特兰数n 对合法括号序列第 n 个卡特兰数n 个元素的出栈序列第 n 个卡特兰数n × n 网格中不越过对角线的路径第 n 个卡特兰数凸 n2 边形的三角剖分方案第 n 个卡特兰数n 个节点的二叉搜索树形态数第 n 个卡特兰数看到这张表你应该能感受到竞赛里的所谓“模型识别”是什么意思题干可以把计数问题包装成一百种样子但核心的递推结构只要长成 f[n] Σ f[k]×f[n-1-k]答案就永远是卡特兰数。判断的关键不是背会这张表而是能从题目里抽出一个“选一个点把问题分成左右两半”的结构。圆上的连线恰好在几何包装下把这个结构呈现得非常清楚。3. 三条路径把卡特兰数彻底吃透这部分写给想真正理解的人。竞赛题解往往只给结论和递推我却建议你把下面三种路径都过一遍因为它们分别对应考场上不同的能力写代码、做证明、快速心算。3.1 路径一直接 DP数据小的时候最稳如果你忘了闭式公式或者题目给的范围很小直接按递推做动态规划完全可行。f[0]1然后双重循环枚举左半边和右半边vectorlong long f(n 1); f[0] 1; for (int i 1; i n; i) { for (int k 0; k i; k) { f[i] f[k] * f[i - 1 - k] % MOD; f[i] % MOD; } }O(n^2) 的复杂度n 到 1000 以内都能跑。优点是逻辑清晰、不需要逆元缺点是决赛题一般不会把范围放这么小。我把它放在第一个是因为大思路永远比公式优先递推式在手哪怕忘了卡特兰数的闭式也能拿到基础分数。3.2 路径二构造括号序列双射看懂“为什么刚好合法”在圆上按顺时针顺序扫描每个点。对每一条弦第一次遇到它的某个端点时记为左括号 (第二次遇到它的另一个端点时记为右括号 )。因为弦互不相交从左往右扫描时当前的切线上一定是“先碰到左端点、后碰到右端点”所以整个序列任意前缀中左括号数量都不小于右括号数量恰好就是一个合法括号序列。反过来任意一个长度为 2n 的括号序列用栈做括号匹配也可以唯一恢复出一组圆上非交叉配对。这说明圆上配对和括号序列之间存在一一对应所以方案数就是第 n 个卡特兰数。注意这里的对应必须固定扫描起点如果从圆上任意一点开始扫同一个配对会因为起点不同产生多个不同的括号序列一一对应就被破坏了。因此标准做法是先把 1 号点固定为起点再做括号序列化。3.3 路径三反射原理算出闭式合法括号序列的数目又等于 C(2n,n) - C(2n,n-1)这个结论来自反射原理。所有长度为 2n、含有 n 个左括号和 n 个右括号的序列总数是 C(2n,n)。其中非法的那些序列在某个前缀第一次出现右括号多于左括号。把从这个位置开始的所有左括号变右括号、右括号变左括号会得到一组含 n-1 个左括号和 n1 个右括号的序列这个变换是可逆的所以非法序列数等于 C(2n,n-1)。两者相减得到C_n C(2n,n) - C(2n,n-1) C(2n,n)/(n1)。到这里卡特兰数的三种身份你已经集齐递推结构、双射模型、组合闭式。接下来进入真正写代码时会踩坑的地方。4. 从闭式到 AC取模实现与两版代码4.1 主解法预处理阶乘和逆元在模数为素数例如 1e97的时候预处理 0! 到 (2n)! 以及它们的逆元然后用组合数公式 C(2n,n) 乘上 (n1) 的逆元即可。C 参考代码如下#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; long long power(long long a, long long b) { long long res 1; while (b 0) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; int m 2 * n; vectorlong long fact(m 1), invfact(m 1); fact[0] 1; for (int i 1; i m; i) { fact[i] fact[i - 1] * i % MOD; } invfact[m] power(fact[m], MOD - 2); for (int i m; i 1; i--) { invfact[i - 1] invfact[i] * i % MOD; } auto comb [](int a, int b) - long long { if (b 0 || b a) return 0; return fact[a] * invfact[b] % MOD * invfact[a - b] % MOD; }; long long ans comb(m, n) * power(n 1, MOD - 2) % MOD; cout ans \n; return 0; }代码本身没什么花哨的复杂度的瓶颈在阶乘数组的预处理和使用快速幂求逆元。如果 n 开到 1e6这个做法完全够用。需要说明的是 ans 的末尾不是直接输出 comb(m,n)因为卡特兰数闭式里分母还有一个 n1这一步忘掉会让答案差出一个逆元的倍数。4.2 Python 版本与卡特兰数线性递推Python 选手可以直接用 math.comb配合费马小定理求逆元from math import comb MOD 10**9 7 n int(input()) ans comb(2 * n, n) * pow(n 1, MOD - 2, MOD) % MOD print(ans)这个写法在 n 不超过十万左右时很省事但 Python 的 math.comb 在 n 很大的时候会创建超大整数内存和计算量都不太好看。更稳妥的做法是用卡特兰数的线性递推式C_i C_{i-1} × (4i - 2) / (i 1)每一步用模逆元处理除法整体 O(n)MOD 10**9 7 n int(input()) c 1 for i in range(1, n 1): c c * (4 * i - 2) % MOD c c * pow(i 1, MOD - 2, MOD) % MOD print(c)这个递推式是从卡特兰数的相邻项比值推导出来的写起来简单也避免了组合数大整数的困扰。在题目允许的前提下提前预处理所有逆元会更省时间。4.3 取模细节里的三个坑第一C 里两个接近 1e9 的数相乘会接近 1e18long long 能装下但务必每一步都取模否则一旦写成 int 相乘直接溢出。第二求逆元的前提是模数为素数且与除数互质1e97 满足条件如果题目给的模数不是素数就不能用费马小定理那个时候就要回到递推 DP 或者用质因数分解来求精确值再取模。第三数组大小要开到 2n1不是 n1我第一次写这道题时顺手开了个 n1结果在 C(2n,n) 这一步当场越界调了很久才发现只是数组少了一个零。5. 变体问题题目改一个条件思路怎么迁移5.1 有若干条边已经固定如果题目额外指定了 m 对点必须连线比如“1 号点和 6 号点必须连3 号点和 5 号点必须连”那答案就不再是完整的卡特兰数。做法是先把这些固定弦画到圆上用它们把圆周切成若干段互相独立的弧每一段弧内部的剩余点必须在内部配对所以每一段的方案数分别是各自弧长一半的卡特兰数最后把所有段的数字乘起来。如果某一段剩余点数为奇数方案直接是 0。举个小例子n4固定 1-4 这条弦。圆被分成两边一边有 2、3 两个点另一边有 5、6、7、8 四个点答案就是 f[1] × f[2] 1 × 2 2。这个变体在蓝桥杯改题时很常见因为它考察的是“固定分割点”而不是“固定起点”模型层面更进一层。5.2 如果不要求全部配对求最大不交弦数有些圆上连线的题并不要求每个点都被连到而是问你最多能连几条互不相交的弦。这种题就完全不是卡特兰数了得回到区间 DP。设 dp[l][r] 表示只在编号 l 到 r 这段弧上选弦的最大数量转移时要么不选 l要么让 l 和某个 k 配对并检查两段内部。转移式长这样dp[l][r] max(dp[l1][r], max_{k in (l1..r)} dp[l1][k-1] dp[k1][r] 1)把“必须全部配对、点数为偶数”的条件去掉卡特兰数的魔法就失效了必须回到通用动态规划。这说明模型边界很重要卡特兰数只在“完整配对”且“点数对称”的前提下成立。5.3 如果问相交弦对的期望数量再换一个问题随机做完美匹配问期望有多少对弦相交。这时候需要往概率方向想。随便取四个点它们内部有三种配对方式只有交叉的那一种会让弦相交而在所有配对中这四个点内部配对的概率可以用乘法原理推导最终期望会落在 n(n-1)/6 量级。这类问题已经不是卡特兰数的直接应用而是线性期望和随机匹配的结合。我在这里提它只是想说明“圆上的连线”四个字之下其实藏着好几个不同难度的问题读题时第一件事永远是确认真实的计数条件。6. 考场识别策略与备赛建议6.1 何时该往卡特兰数上想看到“圆上的点两两连线”“弦互不相交”“括号匹配”“入栈出栈”“二叉树计数”“三角剖分”先在草稿纸上画一个小的实例固定最小的元素试试递推。如果递推长成 f[n] Σ f[k] × f[n-1-k]就直接写闭式。这个流程我在模拟赛里反复验证过比看见几何题先想叉积、先想扫描线要高效得多。6.2 蓝桥杯国赛 A 组的命题风格近几年的决赛题越来越喜欢“短题面 经典模型 取模细节”的组合。它不太考验算法裸模板而是考验你能不能快速把题面翻译成熟悉的组合结构。平时刷题时建议养成分层记录的习惯一道题做完后不记代码记“题干关键词 → 模型 → 复杂度瓶颈”三行话到赛前翻一眼比重新刷一遍更有效。6.3 我在这道题上实际踩过的坑第一次做这题时我犯了两个错。一个是没有意识到“1 号点只能连偶数点”把奇偶性分析省了直接套递推导致边界混乱。另一个是取模时忘掉分母 n1 的逆元样例对不上又找不到原因。后来我给自己立了一条规矩凡是组合数场景写完递推式先把 n1、n2 的小样例手算一遍再对比代码输出两个小样例过了再提交。这个方法治好了我百分之八十的取模失误。6.4 延伸练习清单把下面几道同构题放在一起刷会比单独做这一道收获大得多出栈序列总数、合法括号序列计数、n 个节点二叉搜索树的形态数、凸多边形三角剖分计数、卡特兰数线性递推的取模实现。刷完你会发现卡特兰数不是一道题的答案而是一种“看到二分递归结构就往这里套”的思维习惯。最后说句实在话。每次有读者问“这类题怎么做”我的回答都是同一个不用背模型去画那个最小的图。画完 4 个点连一下再画 6 个点连一下你很快就会亲眼看到 1 号点只能连偶数点、左右两边递归分裂这些结论自己浮出来。卡特兰数不是被记出来的是被画出来的。这道“圆上的连线”放在决赛里大概就是想提醒所有选手这件事。