鸽巢原理在Codeforces刷题中的实战指南：从余数抽屉到值域桶

昨晚又卡在了一道 Div2 C 上，看到题解第一行写着 “By Pigeonhole Principle”，差点没把键盘拍烂。鸽巢原理，这个名字我在入门书里见过，但说实在的，真正在 Codeforces 上刷题时，我很少第一时间往这个方向想。后来陆续整理了一批涉及鸽巢原理的 CF 题，我才意识到它根本不是那种可遇不可求的数学技巧，而是很多题目藏在地板底下的承重墙——一旦看出来，整道题的复杂度直接掉一个量级。

这篇文章我不打算讲教科书式的定理证明，而是直接以刷题为线索，把鸽巢原理在 Codeforces 里的几种常见长相、对应的破题姿势、以及我亲自踩过的坑都梳理一遍。适合的人大概是：rating 1200 到 1700 左右、经常在 Div2 C/D 卡壳、看完题解发现只缺一个“关键观察”的刷题党。

1. 先搞清楚：竞赛里的鸽巢原理到底长什么样

1.1 鸽巢原理的三种表达

教科书版本大家应该都记得：把 n+1 个物体放进 n 个抽屉，至少有一个抽屉放了 2 个物体。

但竞赛里真正常用的是它的两个变体。第一个是数量变体：如果要把 n 个物体放进 m 个盒子，且 n > m，那么至少有一个盒子里有至少 ceil(n/m) 个物体。第二个是模运算变体：如果我有 m 种余数，却生成了 m+1 个数，那么必然有两个数对模 m 同余——这两个数的差就是 m 的倍数。

第三个变体容易被忽略，但出题人特别喜欢用：当一个问题的“答案状态数”远小于“输入规模”时，答案从一开始就已经由鸽巢原理锁死了，你要做的只是把它找出来。这个变体在后面 CF 1500A 那道题里会有非常直观的体现。

我自己的体会是，刷题时不要死记“鸽巢原理”这个名字，而是把它当成一种“数量压过状态数”的直觉：只要某个东西的可能取值只有 K 种，而你手里有超过 K 个样本，那么重复是不可避免的。重复这个词，才是大多数题目的题眼。

1.2 竞赛里最高频的三个“变体”

我把 Codeforces 里跟鸽巢沾边的题粗略分了三类，这三类几乎覆盖了九成以上的情况：

第一类是“余数抽屉”。给定一个数组和一个模数 m，让你判断是否存在某个子序列或连续子段，其和能被 m 整除。这类题的核心就是把前缀和对 m 取模，前缀和数量是 n+1，而余数只有 m 种，一旦 n+1 > m，同余的两个前缀和之间夹的那一段就是答案。CF 577B 就是这个模型的典型代表。

第二类是“值域桶”。问题的答案状态是数值，比如两个数的和，这个和的取值范围有限。当两两组合的数量超过和的取值范围时，一定有两个组合的和重复。CF 1500A 就是拿这个原理把看似不可做的 O(n²) 暴力“安全化”的经典例子。

第三类是“构造保证”。题面里带着“必然存在”“至少有两个”这类字眼，通常解法是先通过鸽巢原理证明答案一定存在，再根据这个存在性去设计构造或者搜索。这种题在 Div2 B/C 里很常见，有时候你证出来存在性之后，连构造都变得顺理成章。

2. 两道必须吃透的 Codeforces 原题

2.1 CF 577B Modulo Sum：n > m 时直接输出 YES 的底气从哪来

这道题我第一次做的时候没往鸽巢想，上去就是裸的背包 DP，结果 n 开到 1e6，直接 MLE。后来才知道，第一步应该先看 n 和 m 的大小关系。

题意很简单：给一个长度为 n 的数组，问是否存在一个非空子序列，使得这个子序列的和能被 m 整除。m 最大只有 1000，但 n 可以很大。很多人第一反应是 DP，因为 m 很小，对余数做背包看起来可行。但 n 大到一定程度时，连输入扫描一遍都嫌多，更别提 DP 了。

关键观察是：如果 n >= m，答案一定是 YES。为什么？考虑数组的前缀和 S[i] = (a[1] + a[2] + ... + a[i]) mod m，再规定 S[0] = 0。这样的前缀和一共有 n+1 个，而余数只有 m 种。当 n >= m 时，n+1 > m，由鸽巢原理，必然存在两个不同的前缀和 S[p] 和 S[q] 满足 S[p] == S[q]。于是 a[p+1] 到 a[q] 这一段的和模 m 为 0，这一段作为子序列是合法的，答案自然就是 YES。

有了这个结论，DP 就只需要在 n < m 的情况下跑。此时 n 最多 999，m 最多 1000，复杂度 O(n*m) 大约 1e6 级别，随便写都能过。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; a[i] %= m; } if (n >= m) { cout << "YES\n"; return 0; } vector<int> dp(m, 0); for (int i = 0; i < n; i++) { vector<int> ndp = dp; ndp[a[i]] = 1; for (int j = 0; j < m; j++) { if (dp[j]) { ndp[(j + a[i]) % m] = 1; } } if (ndp[0]) { cout << "YES\n"; return 0; } dp = move(ndp); } cout << "NO\n"; return 0; }

这段代码里有个细节值得多说一句：ndp[a[i]] = 1 这一行赋值很关键，它保证了子序列可以从当前元素单独出发，不会漏掉“只选一个 a[i]”的情况。但也要注意这行要在循环 j 之前执行，因为 j 的循环里 dp[j] 是上一轮的状态，如果先更新了 ndp 再基于 dp 转移，不会有问题；但如果你贪图省事直接复用 dp 原地转移，就会出现同一个元素被多次使用的错误。

2.2 CF 1500A Going Home：值域桶和鸽巢的正面碰撞

如果说 577B 是“余数抽屉”的教科书，那 1500A 就是“值域桶”的最典型代表。题意是：给定一个长度为 n 的数组 a，找到四个下标 i, j, k, l，两两不同，且满足 a[i] + a[j] = a[k] + a[l]。

n 最大可以到 2e5，值域大约是 2.5e6。直接枚举所有下标对是 O(n²)，显然不可行。但你反过来想：两个数的和能取得多少种不同的值？最大值约为 5e6。也就是说，和的取值空间只有 500 万个，而下标对的数量是 n(n-1)/2，在 n 较大时远超 500 万。由鸽巢原理，必然存在两个不同的下标对具有相同的和。

问题在于，两对下标相同之和，它们的四个下标可能不是互不相同的，比如 (1, 3) 和 (1, 5) 共享了下标 1。这种情况在实现里比想象中常见。我第一次写的时候没注意这个细节，直接找到一个相同和就输出，结果 WA 了一发。

正解的做法是用一个数组或哈希表记录每个和值第一次出现的下标对，然后枚举所有 (i, j)。遇到一个和值已经出现过的，检查之前记录的下标对和当前下标对是否有交集；如果完全没有交集，答案就找到了。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; const int MAX_SUM = 5000005; vector<pair<int, int>> first(MAX_SUM, {-1, -1}); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int s = a[i] + a[j]; if (first[s].first != -1) { auto [x, y] = first[s]; if (x != i && x != j && y != i && y != j) { cout << "YES\n"; cout << x + 1 << " " << y + 1 << " " << i + 1 << " " << j + 1 << "\n"; return 0; } } else { first[s] = {i, j}; } } } cout << "NO\n"; return 0; }

这里有个性能话题值得展开：这个代码表面上是 O(n²)，但实测在 CF 数据下不会超时。原因就在于鸽巢原理——一旦枚举到一定数量的下标对，相同和必然出现，而只要出现一组四个互异下标，程序就直接输出了；如果始终找不到，说明所有相同和的下标对都集中在同几个下标上，这种情况能容纳的下标对数量极其有限，枚举量也被卡在一个可控范围内。换句话说，鸽巢原理在这里不是单纯的理论证明，而是实打实地把最坏情况的枚举规模压下来了。

2.3 顺带一提：n+1 个球放进 n 个格子的直接应用

有个比 1500A 简单得多、但出镜率极高的变体：给你 n+1 个整数，每个数的取值范围是 1 到 n，让你找出任意两个相等的数。这题直接开一个布尔数组标记，遇到重复就输出，看起来简单，但它是很多复杂题的基础模块。

我在 Div2 的 B 题里见过不少这个模型的“马甲”：比如一个数组经过某种变换后变成新数组，要求找重复元素；又比如给你 n 个区间，让你找两个重叠的区间端点。这些题剥掉外壳之后，核心都是“数量超过取值空间，重复必然存在”。把这一层想明白，做题时就不会被各种包装唬住。

3. 把题面翻译成“鸽巢信号”的实战直觉

3.1 看到“至少/必然/存在两个”时的条件反射

很多刷题党一看到“至少存在两个”就觉得这题要构造、要贪心，其实这类措辞往往是鸽巢原理的信号。如果题面里同时出现了“任意”“无论怎么安排”“必然存在”这些词，那八成是先拿鸽巢证一遍存在性，再考虑怎么把这个存在的东西找出来。

我现在的做题习惯是，读完题先把题面里的关键短语划出来：如果出现“至少两个”“必然有”“重复”这类词，我会在草稿纸上单独写一行“Pigeonhole candidate”，然后开始统计：这里面的“数量”和“状态数”分别是什么？数量是不是比状态数多？一旦答案是肯定的，这题的核心思路基本就浮出水面了。

3.2 数量 vs 值域的差值一眼看穿

更通用一点的识别方式是看数量和取值空间的比值。数组长度 n 有 2e5，而某个状态的取值只有 1000 种；组合数有 1e10，而和的取值范围只有 5e6。这些巨大的数量差，就是出题人给你留的门缝。

遇到这种情况，不要急着优化常规算法，先停下来问自己一句：需要处理的“状态”到底有多少种？如果状态数远小于输入规模，鸽巢原理必然会制造重复，而重复往往就是解题的抓手。这比一上来想线段树、二分、数论要直接得多，也快得多。

3.3 前缀和取模：最常用的转化

前缀和取模是鸽巢原理在算法题里最经典、也最容易被忽略的转化方式。只要题目涉及“连续子段能/不能如何如何”而模数又比较小，我就优先想前缀和取模。两个前缀和同余，等价于它们之间的连续段和模 m 为 0。这个转化把“找子段”变成了“找重复的桶”，复杂度往往直接从 O(n²) 降到 O(n)。

但要注意，前缀和取模只能处理连续子段，不能直接处理任意子序列。CF 577B 里 n >= m 的剪枝之所以成立，是因为连续子段本身就是一个合法的子序列；但如果题目要求的是任意选取若干个数，且不要求连续，那前缀和的思路就不够了，需要回到 DP 或其他方法。

4. 我踩过的几个坑

4.1 “四个下标互不相同”看着简单，写起来全是 bug

CF 1500A 的 AC 代码竞争者里，WA 得最多的原因就是下标判重写错。很多人知道要判断 i, j, k, l 互不相同，但写出来的是 p.first != i || p.second != j 这种或逻辑，把“两个下标都不能出现在另一对里”错写成“只要不完全相等就行”。

我自己也栽过一次。记录里存的是 (2, 5)，当前枚举到 (2, 6)，两者只有一个下标重复，本来应该跳过继续找，我却因为 (2, 5) 和 (2, 6) 不完全相同就当成了合法答案。正确写法是：

if (p.first != i && p.first != j && p.second != i && p.second != j)

四个条件缺一不可，任何一个下标出现在另一对里都不行。这个细节值得在本地多造几组数据测一下，比如数组里很多重复值时，非常容易触发这种共享下标的场景。

4.2 子序列、子数组、非空，读题错一个全盘皆输

鸽巢原理相关的题目对“子段”的定义极其敏感。子序列可以不连续，子数组必须连续，非空意味着不能取空集，而“至少两个”意味着至少要有两个元素。这些限定词直接决定前缀和思路能不能用、DP 状态要怎么设计。

CF 577B 这道题，官方题解里 n >= m 直接 YES 的证明用的是连续子段，但因为连续子段也是子序列，所以结论对“子序列”也成立。如果把题目改成“是否存在两个不同的空子序列”，或者改成“恰好一个”，整个结论都会崩掉。我的习惯是做题时先圈出这些限定词，尤其是英文原题里的 subsequence、subarray、non-empty、distinct，绝对不靠猜。

4.3 存在性证明不能当构造用

鸽巢原理告诉你“一定有解”，但它不会告诉你解在哪。CF 577B 的 n >= m 剪枝只负责告诉你不用跑 DP 了，但如果你遇到的是输出方案的版本，还是得老老实实把 DP 跑一遍或者二分找答案。

这一点在高强度刷题时尤其容易误判：我有时候证完存在性就觉得自己会做了，结果发现题目要输出具体下标，还得重新设计算法。鸽巢原理的价值是帮你缩小搜索范围或者直接跳过不可能的情况，但它很少直接给出答案本身。把“证明有解”和“求出解”两件事分开，是避免浪费比赛时间的重要心法。

5. 刷题路线与工具

5.1 Codeforces 里怎么找鸽巢题

Codeforces 的 Problemset 页面可以用标签筛选，鸽巢原理对应的标签是 math 和 combinatorics，但直接筛这两个标签范围太宽，一天刷不完。我的做法是先按难度排序，只看 rating 1200 到 1800 的题，再从里面找题解或 Discussion 里出现过 pigeonhole 字眼的题，逐个做。我自己用过一个叫 Codeforces Better 的增强工具，它能在题目列表里叠加标签和题目评分，筛选效率比原站高不少，方便我做专项统计。

如果你想系统刷，我建议从以下顺序开始：先做 577B 这种“余数抽屉”题，再做 1500A 这种“值域桶”题，然后去 Div2 B/C 里随机挑几道数学标签的题，专门训练从题面措辞里捕捉“数量大于状态数”的感觉。这个顺序是从容易识别的题到需要自己挖掘的题，递进比较舒服。

5.2 我的做题节奏与笔记习惯

我现在做一道涉及鸽巢的题，节奏大致是这样的：前 10 分钟先暴力写一版能过小数据的代码，然后把 n 和 m 这些关键参数拉到极限看一看；如果发现某个状态数很小而数量很大，就停下来写一段“鸽巢检查”——把数量、状态数、可能的重复模式列在草稿纸上。这一步看起来浪费时间，但往往能直接避免在错误方向上花一个小时。

另外我会在笔记软件里专门建一个“抽屉原理”的标签页，每道题只记三行：题目编号、核心的“数量 vs 状态数”对比、以及 AC 代码里最关键的几行。刷到后面，这个笔记本身就成了一个识别系统。比如再看到“n 很大、m 只有 1000”时，我会本能地想到 577B 的模板；看到“两个元素的和”时，会立刻想到值域桶和 pair 判重。

最后再分享一个实战小技巧：在验证鸽巢原理相关的代码时，多用全相同元素构造测试数据。比如 CF 1500A 的数组全为 1，所有二元组和都是 2，这时最容易暴露下标判重 bug，也最能验证你的程序是否能在极端重复下快速退出。我见过不少代码在随机数据上能过，却被全相同的数据卡到超时或 WA，提前用这种数据测一遍，能帮你省下一整场比赛的血压。