鸽巢原理 与 二项式定理

💡 故事背后的算法思想

鸽巢原理是"存在性证明"的万能锤。它不告诉你在哪儿撞，只斩钉截铁地说"一定撞"。竞赛里凡是题目问"是否必然存在""至少有多少"的，第一反应就该是抽屉原理。

二项式定理是"系数计算"的总公式。凡是问"展开式中 xⁿy^m 的系数是多少""所有系数之和是多少"，答案都藏在 C(n,k) 里。它的证明本身就是一次教科书级的组合双计数：把 n 个 (a+b) 相乘，每个括号里选 a 还是选 b，选 k 次 b 的方案数就是 C(n,k)。

两者一个负责"证明存在"，一个负责"算出数目"，合起来就构成了组合数学中最常用的两根杠杆。

📐 证明其实只有一句"反证法"

假设每个盒子里最多放 1 个物体，那么 k 个盒子最多只能放下 k 个物体。但题目说有 n > k 个物体，矛盾！所以至少有一个盒子里放了 ≥ 2 个物体。证毕。

关键理解：鸽巢原理是存在性定理，它保证"有"，但不告诉你是哪一个。想找出具体是哪两个，还得配合算法去枚举或分桶。

反向使用（也是竞赛最爱）：如果要求"保证有重复"，那么物体的数量必须严格大于盒子的数量。反过来，如果要"设计一种无重复的放法"，那就必须 n ≤ k。这一正一反，就是构造题的基本功。

📐 加强形式（广义鸽巢原理）

把 n 个物体放进 k 个盒子，则至少有一个盒子里装的物体个数 ≥ ⌊(n−1)/k⌋ + 1（等价写法：≥ ⌈n/k⌉）。

证明：反证。若每个盒子最多装 ⌊(n−1)/k⌋ 个，那么总共最多装 k·⌊(n−1)/k⌋ ≤ k·(n−1)/k = n−1 个，与"共 n 个"矛盾。所以必有一个盒子的个数 ≥ ⌊(n−1)/k⌋ + 1。

为什么不用 ⌈n/k⌉？两个式子其实恒等（可以自己验算几组数），但 ⌊(n−1)/k⌋+1 在 C++ 里写成 (n-1)/k + 1，整数除法天然向下取整，一行搞定，不用考虑浮点误差。

③ 按子集 / 状态分组（高阶套路）

最常见的两类：把"取了哪些数"编码成 0/1 状态（共 2^m 种，适合状压类问题），或者把前缀和按模 m 的余数分组（共 m 个盒子，n+1 个前缀和 ⇒ 必有同余，从而"存在一段连续区间的和是 m 的倍数"）。第三招是鸽巢原理能与算法真正结合的地方，本讲题 3 会完整实现。

构造抽屉的思考顺序（考场口诀）：先问"结论里的'相同'是什么"→ 那个"相同的东西"就是盒子；再数一共有多少种"相同"，那就是盒子数 k；最后数物体数 n，比较 n 与 k。

🏆 经典结论 1：任取 n+1 个整数，必有两个数之差是 n 的倍数

构造 n 个抽屉：第 r 个抽屉放所有模 n 余 r 的整数（r = 0, 1, …, n−1）。现在有 n+1 个整数，分散到 n 个抽屉中，由鸽巢原理必有两个整数落在同一个抽屉。它们模 n 同余，所以它们的差被 n 整除。

特例（大纲常考的"3 的倍数"版本）：任取 4 个整数，必有两个数之差是 3 的倍数 —— 因为 3 个抽屉（余 0、1、2）装了 4 个数。

例：4 个数 7, 4, 9, 2，模 3 的余数分别是 1, 1, 0, 2。7 与 4 都落在"余 1"抽屉里，差 7−4 = 3，正是 3 的倍数。✔

📅 经典结论 2：生日悖论的直觉修正

很多人误以为"生日问题"比较的是 1/365 与 人数/365，其实比较的是 1/365 与 对数 C(n,2)。当 n = 23 时，C(23,2) = 253，而 253/365 ≈ 0.69，此时"至少一对同生日"的概率已经过半（实际 50.7%）。n = 60 时概率达 99.4%。

精确公式：P(至少一对同生日) = 1 − 365!/((365−n)!·365ⁿ)，当 n > 365 时由鸽巢原理必然为 1。

竞赛意义：这解释了"为什么随机数据下哈希冲突、生日碰撞来得比想象中快得多"——冲突概率随元素个数平方增长，这正是哈希表要选大模数、还是要把冲突概率压到 10⁻⁹ 量级的原因。

🔍 组合证明（比归纳法好懂一百倍）

(a+b)ⁿ 就是 n 个括号 (a+b) 相乘。展开时，每一个括号都要"贡献"一项 —— 要么贡献 a，要么贡献 b。于是总共会得到 2ⁿ 个乘积项（每项都是 aⁱbⁿ⁻ⁱ 的形式）。

把同类项合并：含有 k 个 b 的那些项一共有多少个？答案是在 n 个括号里"选 k 个来出 b"，方案数为 C(n,k)。所以 b^k 前面的系数就是 C(n,k)。

一句话记住：系数 C(n,k) 就是"从 n 个括号中挑 k 个出 b"的方案数。

🔍 代码逐段解析 · C(n,k) 三种求法

法一 initPascal —— 二维数组 C[i][j] 存 C(i,j)，先打边界 C[0][0]=C[i][0]=1，内层用帕斯卡恒等式递推。O(n²) 预处理后每次查询 O(1)。易错：数组开 5005×5005 的 long long 约 200MB，必须模意义下使用或改用滚动数组，且全局数组才不爆栈。

法二 binom —— 先线性筛出 fac/ifac，查询时 fac[n] * ifac[k] % P * ifac[n-k] % P。两处取模缺一不可：三个 long long 相乘会溢出。易错：忘判 k < 0 || k > n，k > n 时 ifac 下标为负，直接 RE。

法三 lucas —— 把 n、m 拆成 p 进制逐位相乘：binom(n%p, m%p) * lucas(n/p, m/p, p)。递归出口 m == 0 返回 1。易错：某一位出现 m%p > n%p 时整个结果就是 0（如 C(100,3) mod 7，100 的 7 进制是 202、3 是 003，最高"位"比较 C(2,3) = 0 → 答案 0）。

⚖️ 从二项式定理"一眼看出"所有性质

把 (a+b)ⁿ = Σ C(n,k)a^n−kb^k 当成一个"参数接口"，代入不同的 a、b 就能刷出一串恒等式：

· 令 a = 1, b = 1 ⇒ (1+1)ⁿ = 2ⁿ = Σ C(n,k)  系数和

· 令 a = 1, b = −1 ⇒ 0 = Σ (−1)^kC(n,k)  交错和

· 令 a = 1, b = x ⇒ (1+x)ⁿ = Σ C(n,k)x^k  母函数

· 两边对 x 求导再令 x = 1 ⇒ Σ k·C(n,k) = n·2ⁿ⁻¹  加权和

· 取 n 为奇数并分离奇偶项 ⇒ 奇数项系数和 = 偶数项系数和 = 2ⁿ⁻¹。

🎨 奇偶性：把杨辉三角涂成黑白，会浮现"谢尔宾斯基三角形"

规则很简单：奇数涂黑，偶数留白。第 0~7 行涂出来是这样（■ = 奇，· = 偶）：

■
■ ■
■ · ■
■ ■ ■ ■
■ · · · ■
■ ■ · · ■ ■
■ · ■ · ■ · ■
■ ■ ■ ■ ■ ■ ■ ■

这不是巧合 —— 它是分形。原因就是前面说的：第 n 行有 2^popcount(n) 个奇数，而这一行共有 n+1 个数。当 n = 2^m−1 时 popcount(n) = m，奇数个数 = 2^m = n+1，整行全奇（图中第 1、3、7 行全是 ■ 的原因）。

竞赛价值：凡是问"C(n,k) 是不是奇数""第 n 行有多少个奇数系数"，答案都在 popcount 里，一行 __builtin_popcountll(n) 就能 O(1) 求出，不用递推！

🔍 代码逐段解析 · 杨辉三角奇偶行

第 1~4 行（读入） —— long long n 接住输入，题目 n ≤ 10⁶ 虽 int 够用，但后面 n - k、位运算统一用 long long 更稳。

第 6~9 行（逐位判定循环） —— k 从 0 扫到 n，判据 (k & (n - k)) == 0：k 与 n−k 没有公共的 1 位（二进制加法 k + (n−k) = n 无进位，即 Kummer 定理的进位次数为 0）⟺ C(n,k) 为奇数。输出 1 或 0，空格分隔。

第 11 行（附加统计） —— 1LL << __builtin_popcountll(n) 直接给出第 n 行奇数总个数 2^popcount(n)；注意必须写 1LL，否则 1 << 40 这类会按 int 溢出。

易错点 1 —— 判据写反：有人写 (k & n) != 0，那是"有公共位"而不是"子掩码"，两者完全不同。

易错点 2 —— 用 __builtin_popcount（32 位版）统计 long long 的 n，高位全被截断。

📐 多项式定理

(x₁ + x₂ + … + x_r)ⁿ = Σ (n; k₁,k₂,…,k_r) · x₁^k₁x₂^k₂…x_r^k_r，求和跑遍所有 k₁+…+k_r = n 的非负整数解。

其中多项式系数：(n; k₁,…,k_r) = n! / (k₁!·k₂!···k_r!)

组合意义（"分堆模型"）：把 n 个不同的小球分给 r 个不同的盒子，第 i 个盒子恰放 k_i 个，方案数就是它。计算时按"从 n 个里选 k₁ 个，再从剩下的里选 k₂ 个…"连乘，化简后得到上面的阶乘形式。

与二项式系数的关系：取 r = 2 就退化回 C(n,k₁) = n!/(k₁!k₂!)，完全一致。

🔍 代码逐段解析 · 多项式系数模板

fpow —— 标准快速幂，每步 % MOD 防溢出，用于费马小定理求单个逆元。

init —— 正推 fac[i] = fac[i-1] * i 建阶乘表；逆元表从后往前：ifac[n] = fpow(fac[n], MOD-2)，再由 ifac[i-1] = ifac[i] * i 倒推（因为 1/i! = 1/(i!) × i = 1/(i−1)!）。一次 O(n) 预处理，之后每次查询 O(r)。

multinom —— 先累加求 n = Σkᵢ，再 fac[n] 乘上每个 ifac[x]。返回值即 (n; k₁,…,kᵣ) mod 1e9+7。

易错点 1 —— fac/ifac 数组大小要按"最大可能的 n"开（代码开了 2×10⁶+6），n 超界同样 RE。

易错点 2 —— 模数必须是素数才能用费马小定理；MOD 是合数时改用扩展欧几里得或 exLucas。

🔍 详细分析过程

第1步：识别模型 —— 结论里的"相同量"是模 n 的余数，所以盒子 = 余数取值，共 n 个盒子（余 0, 1, …, n−1）。

第2步：数物体 —— 有 n+1 个整数，n+1 > n，鸽巢原理生效，必有两个数落在同一个余数盒子里。

第3步：为什么同余 ⟹ 差是倍数 —— 若 a_i ≡ a_j (mod n)，则 a_i − a_j ≡ 0 (mod n)，即差被 n 整除。

第4步：算法实现 —— 开一个大小为 n 的桶 first[r] 记录"余数 r 第一次出现的位置"，遍历时若发现桶已被占用，直接输出两个下标。

第5步：复杂度 —— 时间 O(n)，空间 O(n)。注意输入本身就有 n+1 个数，所以已经是理论最优。

⚠️ 负数取模坑：C++ 中 -7 % 3 == -1（不是 2）。必须写成 ((x % n) + n) % n 才能得到正确的非负余数。

🔍 详细分析过程

第1步：套用二项式定理 —— (ax + by)^k = Σ_t=0..k C(k,t)·(ax)^k−t·(by)^t = Σ C(k,t)·a^k−tb^t·x^k−ty^t。

第2步：对齐指数 —— 题目要 xⁿy^m，所以 k−t = n，即 t = m（这也是为什么题目保证 n+m = k）。

第3步：写出答案 —— 系数 = C(k, m) × aⁿ × b^m mod 10007。

第4步：三块零件怎么算

· C(k, m)：k ≤ 1000，直接杨辉三角 O(k²) 预处理即可，不用逆元。

· aⁿ、b^m：指数最大 1000，但底数达 10⁶，先取模再用快速幂 O(log n)；也可以直接循环乘 1000 次。

第5步：取模时机 —— 乘法前先 a %= 10007、b %= 10007，避免溢出。

复杂度：O(k²) 预处理 + O(log k) 快速幂，k ≤ 1000 时毫秒级通过。

🔍 详细分析过程

问题①：系数之和 —— 直接把 x = 1 代入：(1+1)ⁿ = 2ⁿ = Σ C(n,k)。答案是 2ⁿ，用快速幂 O(log n) 算即可。

问题②：奇数系数个数 —— 需要判定"哪些 k 使 C(n,k) 为奇数"。由 Lucas 定理取模 2：

C(n,k) ≡ C(n₀,k₀)·C(n₁,k₁)·… (mod 2)，其中 n_i、k_i 是二进制各位

而 C(0,0)=1、C(0,1)=0、C(1,0)=1、C(1,1)=1，所以每个二进制位都要求 k_i ≤ n_i。换句话说：k 的二进制必须是 n 的二进制"子掩码"（n 的每个 1 位可以选填 0 或 1，n 的 0 位只能填 0）。

于是 k 的可选个数 = 2^popcount(n)。用 __builtin_popcountll(n) 一行搞定。

两种实现对比：

方法一 暴力递推杨辉三角求每项奇偶：O(n²)，n ≤ 5000 还行。

方法二 位运算：O(log n)，n = 10¹⁸ 也瞬间出答案。推荐。

🔍 代码逐段解析 · 方法一（暴力对拍版）

第 1~3 行 —— 只读一个 n，开 (n+1)×(n+1) 的二维 vector 存组合数的奇偶（每步 % 2，数值只有 0/1，不担心溢出）。

递推循环 —— 标准帕斯卡递推，唯一差别是模数取 2：C[i][j] = (C[i-1][j-1] + C[i-1][j]) % 2。

统计输出 —— odd += C[n][k] 对第 n 行求和，和值就是奇数系数个数。

易错点 —— 这是 O(n²)，只适合 n ≤ 5000 的对拍验证；拿它交 n = 10¹⁸ 的原题必 TLE。它的价值是与方法二互相验证正确性。

方法一双重循环枚举：对每个 i、j 判断 (a_j−a_i) mod m 是否为 0。时间复杂度 O(n²)，n = 2×10⁵ 时约 4×10¹⁰ 次运算，严重超时。

方法二按余数分桶（鸽巢思想）：注意到 a_j − a_i ≡ 0 (mod m) ⟺ a_i ≡ a_j (mod m)。所以"每个余数就是一个抽屉"，桶内任意两数都满足条件。

计数公式：若余数 r 的桶里装了 cnt_r 个数，则它们两两配对贡献 C(cnt_r, 2) = cnt_r·(cnt_r−1)/2 对。答案 = Σ_r C(cnt_r, 2)。

复杂度：时间 O(n)，空间 O(不同余数个数)。因为 m 可达 10⁹ 无法开桶数组，要用 unordered_map 或"排序 + 扫描"。

⚠️ 计数类型：n = 2×10⁵ 时最大可能是 C(n,2) ≈ 2×10¹⁰，必须开 long long。

🔍 代码逐段解析 · 倍数差计数

第 1~4 行（读入） —— n 用 int、m 用 long long（m ≤ 10⁹，恰好压线 int，但后续取模运算统一 long long 更稳）。

第 6~9 行（分桶） —— r = ((x % m) + m) % m 得非负余数，unordered_map 计数。m 最大 10⁹ 不能开数组，map 的 key 是余数、value 是出现次数。

第 11~13 行（累加） —— 对每个桶贡献 c * (c - 1) / 2 即 C(c,2)；c 是 long long，先乘后除不会丢精度也不会溢出。

易错点 1 —— ans 或 c 用 int：n = 2×10⁵ 全同余时答案 C(n,2) ≈ 2×10¹⁰，int 直接变负数。

易错点 2 —— 负数取模没修正：|a_i| ≤ 10⁹ 允许负数，x % m 可能为负，两桶错分。

方法一递推杨辉三角（只存奇偶）：C(n,k) = C(n−1,k−1) + C(n−1,k)，每步 % 2。需要 O(n²) 时间与 O(n) 空间。n = 10⁶ 时 10¹² 次运算，超时，只适合 n ≤ 5000 的对拍。

方法二位运算判定：由 Lucas 定理（模 2），C(n,k) 为奇数 ⟺ k 的二进制是 n 的子掩码，等价写法有三种：

· (k & n) == k  （k 的每个 1 位，n 对应位也是 1）

· (k & (n − k)) == 0  （k 与 n−k 没有公共的 1 位）

· 由 Kummer 定理也可推出同样结论（二进制加法无进位）

复杂度：O(n) 时间（每个 k 判一次），O(1) 额外空间。完美通过。

🔍 代码逐段解析 · 杨辉三角奇偶行

第 1~3 行（读入） —— n ≤ 10⁶，用 long long 接住，后面位运算统一位数。

第 5~9 行（主循环） —— k 从 0 到 n 逐个判定：isOdd = ((k & n) == k)，即 k 是否为 n 的二进制子掩码。输出用 if (k < n) cout << ' ' 控制末尾无多余空格。

统计拓展 —— 若需要奇数总个数，1LL << __builtin_popcountll(n) 一行即可算出 2^popcount(n)，不用再扫一遍（原理见模块二的"奇数个数 = 2^popcount(n)"）。

复杂度 —— O(n) 时间、O(1) 空间，n = 10⁶ 轻松通过。

易错点 1 —— 输出格式：题目要求空格分隔，写成 cout << isOdd << " " 末尾多一个空格可能被判 PE（本代码用条件空格规避）。

易错点 2 —— 把判据写成 (k & n) != 0（有公共位）而非 == k（子掩码），结果完全不同。

方法一枚举左右端点：求出前缀和后枚举所有区间判断模 n 是否为 0，O(n²)。n = 10⁵ 时超时。

方法二前缀和 + 余数抽屉（鸽巢定理的算法化）：

第1步：令 s₀ = 0，s_i = a₁ + … + a_i。共有 n+1 个前缀和。

第2步：把每个 s_i 按 mod n 的余数放进 n 个抽屉里。

第3步：n+1 个对象放进 n 个抽屉，由鸽巢原理必有两个 s_i、s_j（i < j）同余。

第4步：s_j − s_i ≡ 0 (mod n)，而 s_j − s_i 恰好等于 a_i+1 + … + a_j，所以区间 [i+1, j] 就是答案。

复杂度：O(n) 时间、O(n) 空间。而且是确定性构造，不需要随机化。

⚠️ 细节：s 数组要开 long long（10⁵ 个 10⁹ 相加会到 10¹⁴）；负数取模必须写 ((s % n) + n) % n；初始把 pos[0] = 0 放进去，才能正确处理"从第 1 个元素开始"的区间。

🔍 代码逐段解析 · 本讲万能模板

① qpow —— 快速幂模板。额外一行 if (a < 0) a += mod 处理负底数，比裸模板更健壮。

② initComb —— 杨辉三角 O(n²) 建表，n ≤ 5000 适用。注意 C[5005][5005] 的 long long 约 200MB，实际使用时要么降维滚动、要么压缩模数类型，此模板给出的是结构骨架。

③ initFac + binom —— 阶乘逆元法。倒推 ifac[i-1] = ifac[i] * i 是核心技巧；binom 入口的 k < 0 || k > n 防御别删。

④ lucas —— 递归拆 p 进制，要求 p 为素数且 p 不太大（逆元表按 p 建）。

⑤⑥ 鸽巢两个套路 —— 注释即模板：余数分桶记住"负数取模修正"三连 ((x % m) + m) % m；前缀和抽屉记住"s[0]=0 也要进抽屉"。

⑦ 系数奇偶 —— 两行口诀：(k & n) == k 判奇、1LL << popcount(n) 计数，考场上 O(1) 出答案。

易错点 —— ②与③按数据范围二选一，别同时全开（②的数组非常吃内存）；④的 p 必须素数，否则逆元不存在。

拓展 1：子集和是 n 的倍数（鸽巢 + 构造输出方案）

题目：给定 n 和 n 个整数，证明并构造一个非空子集，使其元素和是 n 的倍数。

思路：考察前缀和 s₁, s₂, …, s_n，共 n 个。若某个 s_i ≡ 0 (mod n)，那么前 i 个数就是答案；否则这 n 个前缀和的余数都在 {1,…,n−1} 这 n−1 个抽屉里，由鸽巢原理必有两个同余 s_i ≡ s_j，则 {a_i+1,…,a_j} 是答案。

说明：与正文题 3 的区别是本题只需要"子集"（可以跳着选），而这里构造出来的是连续段，属于子集的特例 —— 结论更强。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i-1] + x; }
    vector<int> pos(n, -1);
    pos[0] = 0;                          // s[0]=0 已在抽屉 0 中
    for (int i = 1; i <= n; i++) {
        int r = ((s[i] % n) + n) % n;
        if (pos[r] != -1) { cout << pos[r] + 1 << " " << i << "\n"; return 0; }
        pos[r] = i;
    }
}

运行：输入 5 / 3 1 4 1 5，前缀和 0, 3, 4, 8, 9, 14，mod 5 = 0, 3, 4, 3, 4, 4 → 冲突在 i=3（pos[3]=1）→ 输出 2 3，区间和 1+4 = 5 ✔

拓展 2：二项式定理求常数项（分数指数）

题目：求 (x + 1/x)ⁿ 展开式中的常数项（即 x 的指数为 0 的项）。

思路：展开 = Σ C(n,k)·x^n−k·x^−k = Σ C(n,k)·x^n−2k。常数项要求 n − 2k = 0，即 k = n/2。所以：n 为奇数时无常数项（答案 0）；n 为偶数时常数项 = C(n, n/2)。这是"指数配平"的典型应用。

// (x + 1/x)^n 的常数项
long long constantTerm(int n) {
    if (n % 2 != 0) return 0;      // 奇数次数 → 无常数项
    return C[n][n / 2];               // 杨辉三角查表
}
// n=4 → C(4,2) = 6；验证 (x+1/x)^4 = x⁴+4x²+6+4/x²+1/x⁴ ✔
// n=5 → 0（无 x⁰ 项）

拓展 3：Kummer 定理 —— 数清楚质因子个数

题目：求 C(n, k) 中含有多少个因子 2（即 2 的指数）。

Kummer 定理：C(n,k) 中质数 p 的指数 = 在 p 进制下做 k 与 n−k 的加法时产生的进位次数。当 p = 2 时，就是二进制加法的进位次数。

快速写法：2 的指数 = popcount(k) + popcount(n−k) − popcount(n)（因为每次进位使二进制中 1 的个数减少一个）。

int expOfTwo(long long n, long long k) {
    return __builtin_popcountll(k) + __builtin_popcountll(n - k)
         - __builtin_popcountll(n);
}
// n=6, k=2 → C(6,2)=15，pc(2)+pc(4)-pc(6) = 1+1-2 = 0 ✔（15 是奇数）
// n=10,k=2 → C(10,2)=45，1+1-2 = 0 ✔
// n=10,k=3 → C(10,3)=120=8×15，pc(3)+pc(7)-pc(10) = 2+3-2 = 3 ✔（2³=8 整除）

用途：当题目要求 C(n,k) 的奇偶性、或求阶乘/组合数的质因子分布时，Kummer 定理能把 O(n) 的统计降为 O(1) 位运算。