拓冰网站定制 
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载容斥原理是组合数学中用于计算多个集合并集元素数目的核心工具其思想在 LeetCode 的计数类题目中有着极其广泛的应用。本文以「宫水三叶的刷题日记」仓库中的容斥原理专题索引为核心骨架结合仓库内多篇完整题解的源码实现系统讲解容斥原理的基础公式、与二分/数位 DP/前缀和的组合套路并附上专题全部题目索引帮助读者建立「识别容斥 → 构造补集 → 二分/DP 加速」的完整解题链路。一、容斥原理的本质从并集计数到补集思想容斥原理Inclusion–Exclusion Principle解决的问题是如何不重不漏地统计多个集合并集的元素个数。当多个集合之间存在重叠时直接相加必然重复计数容斥原理给出了精确的修正公式。对于两个集合 $A$、$B$其并集大小为$$ |A \cup B| |A| |B| - |A \cap B| $$推广到三个集合$$ |A \cup B \cup C| |A| |B| |C| - |A \cap B| - |A \cap C| - |B \cap C| |A \cap B \cap C| $$一般地$n$ 个集合的并集等于「所有奇数个集合交集大小之和」减去「所有偶数个集合交集大小之和」即奇加偶减。在 LeetCode 计数类问题中容斥原理有两种典型用法正向容斥直接统计满足某性质如「能被 a 或 b 整除」的元素个数通过「加两个单条件、减一个双条件」消除重叠补集容斥当直接统计复杂时先统计「补集」如「至少 1 位重复数字」的对立面「各位数字都不同」再用总数减去补集如 1012. 至少有 1 位重复的数字 所采用的思想。仓库中的 Index/容斥原理.md 专题索引收录了 40 道涉及该思想的中高难度题目覆盖了「容斥 × 二分」「容斥 × 数位 DP」「容斥 × 前缀和」三大高频组合套路。二、正向容斥的经典模板能被 a 或 b 整除的数8782.1 题目核心求第 n 个神奇数字第 N 个神奇数字 是「容斥原理 × 二分」组合的教科书级题目一个正整数如果能被a或b整除那么它是神奇的。给定n、a、b返回第n个神奇数字对 $10^9 7$ 取模的值其中 $1 \le n \le 10^9$$2 \le a, b \le 4 \times 10^4$。题解见 878 题解全文给出了完整的推导链第一步排除线性做法。若不看数据范围容易想到「多路归并」——用两个指针分别指向 $[a, 2a, 3a, \dots]$ 和 $[b, 2b, 3b, \dots]$不断比较指针指向值的大小并推进计数。该做法复杂度为 $O(n)$对 $n 10^9$ 的数据范围完全不可行。第二步寻找二段性确定二分。要在「能被 a 或 b 整除的数」形成的数轴上二分找第 $n$ 个需要定义一种性质使得分割点 $k$ 左侧满足、右侧不满足小于 $k$ 的任意数字 $x$ 满足 $[0, x]$ 内符合要求的数不足 $k$ 个大于等于 $k$ 的 $x$ 不满足。该性质天然具备单调性二分成立。第三步用容斥原理实现高效 check。关键在于快速回答「$[0, n]$ 中有多少个数能被 a 或 b 整除」这正是容斥原理的双集合标准式$$ \left \lfloor \frac{n}{a} \right \rfloor \left \lfloor \frac{n}{b} \right \rfloor - \left \lfloor \frac{n}{c} \right \rfloor $$其中 $c$ 为 $a$ 和 $b$ 的最小公倍数LCM——只有同时被 $a$、$b$ 整除的数才在交集里而能被两者同时整除等价于能被 $\mathrm{lcm}(a, b)$ 整除。第四步求解 lcm 需要 gcd。题解给出了两个基础模板int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); }第五步确定二分值域。合格的值域只需保证答案落在其中可直接取 $10^{18}$也可根据数据范围收紧为 $[0, 40000n]$取 $a$、$b$ 中较大值 $m$第 $n$ 个神奇数字最大不超过 $n \times m$。2.2 完整可运行代码仓库原文四语言版本仓库题解提供了 Java / C / Python3 / TypeScript 四种语言的完整实现以下为核心逻辑Java 版出处见 878 题解class Solution { int n, a, b, c; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } public int nthMagicalNumber(int _n, int _a, int _b) { n _n; a _a; b _b; c a * b / gcd(a, b); long l 0, r (long)1e18; while (l r) { long mid l r 1; if (check(mid) n) r mid; else l mid 1; } return (int)(r % 1000000007); } long check(long x) { return x / a x / b - x / c; } }时间复杂度$O(\log N)$其中 $N 10^{18}$ 为值域大小空间复杂度$O(1)$。要点提炼check函数的三项式就是「单条件相加、双条件相减」的容斥公式注意lcm计算中a * b可能溢出实际工程中可改用a / gcd(a, b) * b的写法仓库模板以算法演示为主读者在 Java 大数场景下可自行加保护。三、容斥 × 二分统计阶乘尾部零的个数793阶乘函数后 K 个零 展示了容斥原理在数论中的另一个形态——筛除重复计数。题目要求给定 $k$$0 \le k \le 10^9$统计满足 $f(x) k$ 的非负整数 $x$ 的数量其中 $f(x)$ 是 $x!$ 末尾 0 的个数。核心推导详见 793 题解$n!$ 末尾 0 的个数取决于质因数分解中 $10 2 \times 5$ 的对数。由于 $2$ 的个数恒不少于 $5$ 的个数$p \ge q$ 始终成立因此末尾 0 的个数等于质因数 $5$ 的个数 $q$随着 $x$ 增大$x!$ 分解出的 5 的个数单调不减具备二段性可二分计数函数采用连除筛法long getCnt(long x) { long ans 0; while (x ! 0) { ans x / 5; x / 5; } return ans; }即 $\lfloor x/5 \rfloor \lfloor x/25 \rfloor \lfloor x/125 \rfloor \dots$这本质上是「容斥」思想的数论版先算所有 5 的倍数贡献 1 个 5再补算 25 的倍数额外贡献 1 个再补算 125 的倍数……逐层补上重复因子。答案用「前缀差」得到定义f(k)为阶乘分解中 5 的个数小于等于k的 $x$ 的个数则答案 $ f(k) - f(k-1)$值域上界取 $10^{10}$由 $k \le 10^9$ 放大得到。该题同时给出了 Java / C / Python / TypeScript 四版本实现读者可对照 仓库原文 查阅。注意二分时使用l r 1 1的「找右侧端点」模板因为f是「小于等于」型前缀函数。四、容斥 × 数位 DP区间计数问题的通用范式数位 DP 与容斥的结合是专题中最常见的套路其核心公式出现在多篇题解中$$ ans_{(l, r)} dp(r) - dp(l - 1) $$即任意区间 $[l, r]$ 的合法数个数 前缀函数 $dp$ 在右端点的值减去左端点前一个位置的值。这本质上就是「总数 - 补集」的容斥思想在数位维度上的应用。4.1 各位数字都不相同的数字个数357统计各位数字都不同的数字个数 给出两层递进做法做法一乘法原理$O(n)$。由于不能含前导 0最高位有 9 种选择从次高位起可选个数从 9 开始逐一递减9、8、7、……每位数可选的个数相乘即为长度为 $n$ 的方案数累加所有长度 $[1, n]$ 即为答案class Solution { public int countNumbersWithUniqueDigits(int n) { if (n 0) return 1; int ans 10; for (int i 2, last 9; i n; i) { int cur last * (10 - i 1); ans cur; last cur; } return ans; } }做法二数位 DP 容斥可回答任意区间。实现int dp(int x)返回 $[0, x]$ 内合法数个数将合法数分成三类统计res1位数与 $x$ 相同且最高位小于 $x$ 最高位res2位数与 $x$ 相同且最高位等于 $x$ 最高位重点res3位数比 $x$ 少。对 $x$ 从高到低逐位处理在第 $k$ 位为满足「大小限制」只能在 $[0, cur-1]$ 取数同时用int s的低 10 位记录数字 $[0,9]$ 的使用情况以满足「去重限制」二者同时满足的个数记为cnt确定第 $k$ 位后剩余位数可任意组合用预处理的乘积数组f[l][r] l × (l1) × … × r加速查询。完整实现见 357 题解。4.2 不含连续 1 的非负整数600不含连续1的非负整数 将同一范式推广到二进制数位 DP题解明确指出对于「数位 DP」题都存在「询问 $[a, b]$ 区间内符合条件的数值个数」的一般形式通常实现int dp(int x)后应用容斥原理求解$dp(b) - dp(a - 1)$。实现细节用static预处理f[i][j]二进制长度为 $i$ 且最高位为 $j$ 的合法数个数处理 $n$ 的每一位时——若当前位为 1则该位填 0 时低位可任意填查表累加f[i1][0]同时用prev记录上一位一旦出现连续两个 1 立即 break。时间复杂度 $O(\log n)$空间复杂度 $O(C)$$C 50 \times 2$。详见 600 题解。4.3 至少有 1 位重复的数字1012至少有 1 位重复的数字 是「补集容斥」的直接示范$$ \text{至少 1 位重复的数} n - \text{各位数字都不相同的数} $$题解将「没有重复数」的求解显式引用到 357 题的进阶部分dp(r) - dp(l-1)公式在 1012 题解 中原样出现实现上同样分为res1/res2/res3三类统计把「总数减补集」的容斥思想与数位 DP 的按位处理无缝衔接。五、容斥 × 前缀和 / 区间统计二维矩阵与子数组的并集计数专题索引中还包含大量「容斥 × 前缀和」类题目其核心同样是「重复计数的修正」二维区域和检索 - 矩阵不可变二维前缀和的核心公式即为容斥原理——子矩阵和sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] sum[r1-1][c1-1]加回被减去两次的左上角区域正是「奇加偶减」的直接体现区域和检索 - 数组不可变一维前缀和的sum[r] - sum[l-1]是区间查询的基础形态区域和检索 - 数组可修改将前缀和扩展到「树状数组/线段树」支持单点更新的变体矩形区域不超过 K 的最大数值和枚举矩阵上下边界 前缀和 有序集合是二维容斥与二分查找的组合应用元素和为目标值的子矩阵数量二维前缀和 哈希表优化把「子矩阵和等于 target」转化为前缀和的计数问题。此类题目在 Index/前缀和.md 专题中亦有交叉收录两篇索引可以对照阅读体会同一公式在不同专题语境下的统一性。六、专题题目索引来自 Index/容斥原理.md 全表下表完整继承自 Index/容斥原理.md包含题目、难度与推荐指数供按需检索题目难度推荐指数187. 重复的DNA序列中等304. 二维区域和检索 - 矩阵不可变中等303. 区域和检索 - 数组不可变简单307. 区域和检索 - 数组可修改中等354. 俄罗斯套娃信封问题困难357. 统计各位数字都不同的数字个数中等363. 矩形区域不超过 K 的最大数值和困难437. 路径总和 III中等523. 连续的子数组和中等525. 连续数组中等528. 按权重随机选择中等600. 不含连续1的非负整数困难629. K个逆序对数组中等661. 图片平滑器简单673. 最长递增子序列的个数中等689. 三个无重叠子数组的最大和困难724. 寻找数组的中心下标简单793. 阶乘函数后 K 个零困难825. 适龄的朋友中等878. 第 N 个神奇数字困难926. 将字符串翻转到单调递增中等930. 和相同的二元子数组中等1004. 最大连续1的个数 III中等1074. 元素和为目标值的子矩阵数量困难1012. 至少有 1 位重复的数字困难1154. 一年中的第几天简单1208. 尽可能使字符串相等中等1310. 子数组异或查询中等1395. 统计作战单位数中等1442. 形成两个异或相等数组的三元组数目中等1480. 一维数组的动态和简单1588. 所有奇数长度子数组的和简单1738. 找出第 K 大的异或坐标值中等1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗中等1749. 任意子数组和的绝对值的最大值中等1838. 最高频元素的频数中等1893. 检查是否区域内所有整数都被覆盖简单1894. 找到需要补充粉笔的学生编号中等2055. 蜡烛之间的盘子中等2100. 适合打劫银行的日子中等表格使用说明该索引中的题目按「是否涉及重叠计数」归类部分题目如 304、303、307、363、1074、1310、1738 等同时收录于 Index/前缀和.md 与 Index/位运算.md 等其他专题交叉索引的设计便于读者从不同算法视角反复咀嚼同一道题。七、实战方法论四步识别容斥原理题综合上述题解源码可以提炼出识别与求解容斥原理题的通用流程判断计数语义题目要求统计「满足条件 A 或 B」「至少一个条件」「区间内合法数」等且条件之间存在重叠时优先考虑容斥构造补集当「满足条件」难统计而「不满足条件」好统计时如 1012 的「重复数字」与「全不同数字」用总数 - 补集选择加速工具计数函数具备单调性如 878 的神奇数字、793 的阶乘零→ 二分 $O(1)$ 容斥公式涉及数位限制与去重如 357、600、1012→ 数位 DP dp(r) - dp(l-1)涉及区间/矩阵和如 304、363、1074→ 前缀和 容斥修正重叠区域验证边界注意 lcm 溢出a/gcd * b、二分值域上界如 $10^{18}$ 或n × max(a,b)、static预处理打表如 357 的乘积数组、600 的f数组等工程细节。八、总结容斥原理并非孤立的知识点它在仓库题解中呈现出「公式恒定、载体多变」的特征同样的「奇加偶减」可以落在整除计数878、阶乘质因数793、二进制数位600、十进制数位357、1012、二维矩阵前缀和304、363等完全不同的问题载体上。通过本文对 Index/容斥原理.md 专题索引的深度展开读者可以沿两条路径继续深入学习一是按上表逐题精读仓库内完整题解每篇均含多语言可运行代码与复杂度分析二是横向对照 Index/数位%20DP.md、Index/前缀和.md、Index/二分.md 等交叉专题建立以「重叠计数修正」为核心的统一算法认知。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode压缩算法原理LogicStack LeetCode压缩算法原理 在数据处理和存储中压缩算法Compression Algorithm是提高效率的关键技术。它通过消除教程文档LogicStack-LeetCode高精度计算在算法中的实现LogicStack LeetCode高精度计算在算法中的实现 在算法竞赛和工程实践中当遇到超过编程语言内置数据类型表示范围的数值计算时高精度计算Hig教程文档可视化AI工作流架构解析Dify平台下的46个模块化工作流技术实现可视化AI工作流架构解析Dify平台下的46个模块化工作流技术实现 Awesome Dify Workflow项目通过46个精心设计的YAML工作流文件构建示例工程上一篇5步掌握kohya_ss训练可视化AI模型调优终极指南下一篇Windows10Debloater终极指南一键清理Windows 10系统垃圾恢复流畅体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 容斥原理在算法题解中的应用：LogicStack-LeetCode 刷题笔记深度解析
教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载容斥原理是组合数学中用于计算多个集合并集元素数目的核心工具其思想在 LeetCode 的计数类题目中有着极其广泛的应用。本文以「宫水三叶的刷题日记」仓库中的容斥原理专题索引为核心骨架结合仓库内多篇完整题解的源码实现系统讲解容斥原理的基础公式、与二分/数位 DP/前缀和的组合套路并附上专题全部题目索引帮助读者建立「识别容斥 → 构造补集 → 二分/DP 加速」的完整解题链路。一、容斥原理的本质从并集计数到补集思想容斥原理Inclusion–Exclusion Principle解决的问题是如何不重不漏地统计多个集合并集的元素个数。当多个集合之间存在重叠时直接相加必然重复计数容斥原理给出了精确的修正公式。对于两个集合 $A$、$B$其并集大小为$$ |A \cup B| |A| |B| - |A \cap B| $$推广到三个集合$$ |A \cup B \cup C| |A| |B| |C| - |A \cap B| - |A \cap C| - |B \cap C| |A \cap B \cap C| $$一般地$n$ 个集合的并集等于「所有奇数个集合交集大小之和」减去「所有偶数个集合交集大小之和」即奇加偶减。在 LeetCode 计数类问题中容斥原理有两种典型用法正向容斥直接统计满足某性质如「能被 a 或 b 整除」的元素个数通过「加两个单条件、减一个双条件」消除重叠补集容斥当直接统计复杂时先统计「补集」如「至少 1 位重复数字」的对立面「各位数字都不同」再用总数减去补集如 1012. 至少有 1 位重复的数字 所采用的思想。仓库中的 Index/容斥原理.md 专题索引收录了 40 道涉及该思想的中高难度题目覆盖了「容斥 × 二分」「容斥 × 数位 DP」「容斥 × 前缀和」三大高频组合套路。二、正向容斥的经典模板能被 a 或 b 整除的数8782.1 题目核心求第 n 个神奇数字第 N 个神奇数字 是「容斥原理 × 二分」组合的教科书级题目一个正整数如果能被a或b整除那么它是神奇的。给定n、a、b返回第n个神奇数字对 $10^9 7$ 取模的值其中 $1 \le n \le 10^9$$2 \le a, b \le 4 \times 10^4$。题解见 878 题解全文给出了完整的推导链第一步排除线性做法。若不看数据范围容易想到「多路归并」——用两个指针分别指向 $[a, 2a, 3a, \dots]$ 和 $[b, 2b, 3b, \dots]$不断比较指针指向值的大小并推进计数。该做法复杂度为 $O(n)$对 $n 10^9$ 的数据范围完全不可行。第二步寻找二段性确定二分。要在「能被 a 或 b 整除的数」形成的数轴上二分找第 $n$ 个需要定义一种性质使得分割点 $k$ 左侧满足、右侧不满足小于 $k$ 的任意数字 $x$ 满足 $[0, x]$ 内符合要求的数不足 $k$ 个大于等于 $k$ 的 $x$ 不满足。该性质天然具备单调性二分成立。第三步用容斥原理实现高效 check。关键在于快速回答「$[0, n]$ 中有多少个数能被 a 或 b 整除」这正是容斥原理的双集合标准式$$ \left \lfloor \frac{n}{a} \right \rfloor \left \lfloor \frac{n}{b} \right \rfloor - \left \lfloor \frac{n}{c} \right \rfloor $$其中 $c$ 为 $a$ 和 $b$ 的最小公倍数LCM——只有同时被 $a$、$b$ 整除的数才在交集里而能被两者同时整除等价于能被 $\mathrm{lcm}(a, b)$ 整除。第四步求解 lcm 需要 gcd。题解给出了两个基础模板int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int lcm(int a, int b) { return a * b / gcd(a, b); }第五步确定二分值域。合格的值域只需保证答案落在其中可直接取 $10^{18}$也可根据数据范围收紧为 $[0, 40000n]$取 $a$、$b$ 中较大值 $m$第 $n$ 个神奇数字最大不超过 $n \times m$。2.2 完整可运行代码仓库原文四语言版本仓库题解提供了 Java / C / Python3 / TypeScript 四种语言的完整实现以下为核心逻辑Java 版出处见 878 题解class Solution { int n, a, b, c; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } public int nthMagicalNumber(int _n, int _a, int _b) { n _n; a _a; b _b; c a * b / gcd(a, b); long l 0, r (long)1e18; while (l r) { long mid l r 1; if (check(mid) n) r mid; else l mid 1; } return (int)(r % 1000000007); } long check(long x) { return x / a x / b - x / c; } }时间复杂度$O(\log N)$其中 $N 10^{18}$ 为值域大小空间复杂度$O(1)$。要点提炼check函数的三项式就是「单条件相加、双条件相减」的容斥公式注意lcm计算中a * b可能溢出实际工程中可改用a / gcd(a, b) * b的写法仓库模板以算法演示为主读者在 Java 大数场景下可自行加保护。三、容斥 × 二分统计阶乘尾部零的个数793阶乘函数后 K 个零 展示了容斥原理在数论中的另一个形态——筛除重复计数。题目要求给定 $k$$0 \le k \le 10^9$统计满足 $f(x) k$ 的非负整数 $x$ 的数量其中 $f(x)$ 是 $x!$ 末尾 0 的个数。核心推导详见 793 题解$n!$ 末尾 0 的个数取决于质因数分解中 $10 2 \times 5$ 的对数。由于 $2$ 的个数恒不少于 $5$ 的个数$p \ge q$ 始终成立因此末尾 0 的个数等于质因数 $5$ 的个数 $q$随着 $x$ 增大$x!$ 分解出的 5 的个数单调不减具备二段性可二分计数函数采用连除筛法long getCnt(long x) { long ans 0; while (x ! 0) { ans x / 5; x / 5; } return ans; }即 $\lfloor x/5 \rfloor \lfloor x/25 \rfloor \lfloor x/125 \rfloor \dots$这本质上是「容斥」思想的数论版先算所有 5 的倍数贡献 1 个 5再补算 25 的倍数额外贡献 1 个再补算 125 的倍数……逐层补上重复因子。答案用「前缀差」得到定义f(k)为阶乘分解中 5 的个数小于等于k的 $x$ 的个数则答案 $ f(k) - f(k-1)$值域上界取 $10^{10}$由 $k \le 10^9$ 放大得到。该题同时给出了 Java / C / Python / TypeScript 四版本实现读者可对照 仓库原文 查阅。注意二分时使用l r 1 1的「找右侧端点」模板因为f是「小于等于」型前缀函数。四、容斥 × 数位 DP区间计数问题的通用范式数位 DP 与容斥的结合是专题中最常见的套路其核心公式出现在多篇题解中$$ ans_{(l, r)} dp(r) - dp(l - 1) $$即任意区间 $[l, r]$ 的合法数个数 前缀函数 $dp$ 在右端点的值减去左端点前一个位置的值。这本质上就是「总数 - 补集」的容斥思想在数位维度上的应用。4.1 各位数字都不相同的数字个数357统计各位数字都不同的数字个数 给出两层递进做法做法一乘法原理$O(n)$。由于不能含前导 0最高位有 9 种选择从次高位起可选个数从 9 开始逐一递减9、8、7、……每位数可选的个数相乘即为长度为 $n$ 的方案数累加所有长度 $[1, n]$ 即为答案class Solution { public int countNumbersWithUniqueDigits(int n) { if (n 0) return 1; int ans 10; for (int i 2, last 9; i n; i) { int cur last * (10 - i 1); ans cur; last cur; } return ans; } }做法二数位 DP 容斥可回答任意区间。实现int dp(int x)返回 $[0, x]$ 内合法数个数将合法数分成三类统计res1位数与 $x$ 相同且最高位小于 $x$ 最高位res2位数与 $x$ 相同且最高位等于 $x$ 最高位重点res3位数比 $x$ 少。对 $x$ 从高到低逐位处理在第 $k$ 位为满足「大小限制」只能在 $[0, cur-1]$ 取数同时用int s的低 10 位记录数字 $[0,9]$ 的使用情况以满足「去重限制」二者同时满足的个数记为cnt确定第 $k$ 位后剩余位数可任意组合用预处理的乘积数组f[l][r] l × (l1) × … × r加速查询。完整实现见 357 题解。4.2 不含连续 1 的非负整数600不含连续1的非负整数 将同一范式推广到二进制数位 DP题解明确指出对于「数位 DP」题都存在「询问 $[a, b]$ 区间内符合条件的数值个数」的一般形式通常实现int dp(int x)后应用容斥原理求解$dp(b) - dp(a - 1)$。实现细节用static预处理f[i][j]二进制长度为 $i$ 且最高位为 $j$ 的合法数个数处理 $n$ 的每一位时——若当前位为 1则该位填 0 时低位可任意填查表累加f[i1][0]同时用prev记录上一位一旦出现连续两个 1 立即 break。时间复杂度 $O(\log n)$空间复杂度 $O(C)$$C 50 \times 2$。详见 600 题解。4.3 至少有 1 位重复的数字1012至少有 1 位重复的数字 是「补集容斥」的直接示范$$ \text{至少 1 位重复的数} n - \text{各位数字都不相同的数} $$题解将「没有重复数」的求解显式引用到 357 题的进阶部分dp(r) - dp(l-1)公式在 1012 题解 中原样出现实现上同样分为res1/res2/res3三类统计把「总数减补集」的容斥思想与数位 DP 的按位处理无缝衔接。五、容斥 × 前缀和 / 区间统计二维矩阵与子数组的并集计数专题索引中还包含大量「容斥 × 前缀和」类题目其核心同样是「重复计数的修正」二维区域和检索 - 矩阵不可变二维前缀和的核心公式即为容斥原理——子矩阵和sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] sum[r1-1][c1-1]加回被减去两次的左上角区域正是「奇加偶减」的直接体现区域和检索 - 数组不可变一维前缀和的sum[r] - sum[l-1]是区间查询的基础形态区域和检索 - 数组可修改将前缀和扩展到「树状数组/线段树」支持单点更新的变体矩形区域不超过 K 的最大数值和枚举矩阵上下边界 前缀和 有序集合是二维容斥与二分查找的组合应用元素和为目标值的子矩阵数量二维前缀和 哈希表优化把「子矩阵和等于 target」转化为前缀和的计数问题。此类题目在 Index/前缀和.md 专题中亦有交叉收录两篇索引可以对照阅读体会同一公式在不同专题语境下的统一性。六、专题题目索引来自 Index/容斥原理.md 全表下表完整继承自 Index/容斥原理.md包含题目、难度与推荐指数供按需检索题目难度推荐指数187. 重复的DNA序列中等304. 二维区域和检索 - 矩阵不可变中等303. 区域和检索 - 数组不可变简单307. 区域和检索 - 数组可修改中等354. 俄罗斯套娃信封问题困难357. 统计各位数字都不同的数字个数中等363. 矩形区域不超过 K 的最大数值和困难437. 路径总和 III中等523. 连续的子数组和中等525. 连续数组中等528. 按权重随机选择中等600. 不含连续1的非负整数困难629. K个逆序对数组中等661. 图片平滑器简单673. 最长递增子序列的个数中等689. 三个无重叠子数组的最大和困难724. 寻找数组的中心下标简单793. 阶乘函数后 K 个零困难825. 适龄的朋友中等878. 第 N 个神奇数字困难926. 将字符串翻转到单调递增中等930. 和相同的二元子数组中等1004. 最大连续1的个数 III中等1074. 元素和为目标值的子矩阵数量困难1012. 至少有 1 位重复的数字困难1154. 一年中的第几天简单1208. 尽可能使字符串相等中等1310. 子数组异或查询中等1395. 统计作战单位数中等1442. 形成两个异或相等数组的三元组数目中等1480. 一维数组的动态和简单1588. 所有奇数长度子数组的和简单1738. 找出第 K 大的异或坐标值中等1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗中等1749. 任意子数组和的绝对值的最大值中等1838. 最高频元素的频数中等1893. 检查是否区域内所有整数都被覆盖简单1894. 找到需要补充粉笔的学生编号中等2055. 蜡烛之间的盘子中等2100. 适合打劫银行的日子中等表格使用说明该索引中的题目按「是否涉及重叠计数」归类部分题目如 304、303、307、363、1074、1310、1738 等同时收录于 Index/前缀和.md 与 Index/位运算.md 等其他专题交叉索引的设计便于读者从不同算法视角反复咀嚼同一道题。七、实战方法论四步识别容斥原理题综合上述题解源码可以提炼出识别与求解容斥原理题的通用流程判断计数语义题目要求统计「满足条件 A 或 B」「至少一个条件」「区间内合法数」等且条件之间存在重叠时优先考虑容斥构造补集当「满足条件」难统计而「不满足条件」好统计时如 1012 的「重复数字」与「全不同数字」用总数 - 补集选择加速工具计数函数具备单调性如 878 的神奇数字、793 的阶乘零→ 二分 $O(1)$ 容斥公式涉及数位限制与去重如 357、600、1012→ 数位 DP dp(r) - dp(l-1)涉及区间/矩阵和如 304、363、1074→ 前缀和 容斥修正重叠区域验证边界注意 lcm 溢出a/gcd * b、二分值域上界如 $10^{18}$ 或n × max(a,b)、static预处理打表如 357 的乘积数组、600 的f数组等工程细节。八、总结容斥原理并非孤立的知识点它在仓库题解中呈现出「公式恒定、载体多变」的特征同样的「奇加偶减」可以落在整除计数878、阶乘质因数793、二进制数位600、十进制数位357、1012、二维矩阵前缀和304、363等完全不同的问题载体上。通过本文对 Index/容斥原理.md 专题索引的深度展开读者可以沿两条路径继续深入学习一是按上表逐题精读仓库内完整题解每篇均含多语言可运行代码与复杂度分析二是横向对照 Index/数位%20DP.md、Index/前缀和.md、Index/二分.md 等交叉专题建立以「重叠计数修正」为核心的统一算法认知。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode压缩算法原理LogicStack LeetCode压缩算法原理 在数据处理和存储中压缩算法Compression Algorithm是提高效率的关键技术。它通过消除教程文档LogicStack-LeetCode高精度计算在算法中的实现LogicStack LeetCode高精度计算在算法中的实现 在算法竞赛和工程实践中当遇到超过编程语言内置数据类型表示范围的数值计算时高精度计算Hig教程文档可视化AI工作流架构解析Dify平台下的46个模块化工作流技术实现可视化AI工作流架构解析Dify平台下的46个模块化工作流技术实现 Awesome Dify Workflow项目通过46个精心设计的YAML工作流文件构建示例工程上一篇5步掌握kohya_ss训练可视化AI模型调优终极指南下一篇Windows10Debloater终极指南一键清理Windows 10系统垃圾恢复流畅体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考