★ FEATURED ARTICLE 1. 从一道题看位运算与组合数学的交叉玩法第一次看到“数学作业”这个标题很多人会以为是一道纯数论或者纯组合计数的题目但真正翻开题面之后才会发现它把位运算和组合数学这两块看似不太搭边的内容揉在了一起。这种出题思路在竞赛题里其实很常见位运算负责把问题拆成一个个独立的二进制位组合数学负责在每个位上做计数和累加最后再把所有位的结果拼回一个整数。整道题的核心难点不在于某个单一算法有多深而在于你能不能看穿“按位独立”这个关键性质并且把组合计数的公式推对。这篇文章我会从零开始拆解这道题的完整思路包括为什么可以按位拆、每一位上的贡献怎么算、组合数怎么预处理、边界情况怎么处理以及我在实际写这道题时踩过的坑。适合已经掌握基础位运算和组合数预处理、但遇到这种“位运算计数”混合题容易卡住的读者。如果你正在准备算法竞赛或者单纯想找一道题来练手位运算与组合数学的结合这道题是个不错的样本。2. 题目核心需求的拆解与整体设计思路2.1 题目到底在问什么先把问题抽象一下。题目给定一个数组要求你计算所有子集的某种“按位异或和”再求和或者类似形式的按位贡献累加。具体形式可能因版本不同略有差异但核心结构是一致的你需要对每一个二进制位单独统计在所有可能的子集或子序列、或某种选取方式中这一位最终对答案贡献了多少次。这类题目的通用套路是把整体求和拆成每一位的贡献之和。因为异或、与、或这些位运算在位上具有独立性——第 k 位的结果只取决于所有数第 k 位的取值和其他位完全无关。这个性质是整道题能够高效求解的根基。2.2 为什么可以按位独立处理这里需要把“按位独立”这件事说透。假设我们有一个数组 a长度是 n。对于异或运算来说第 k 位的异或结果等于所有数第 k 位异或起来的结果。也就是说如果你只关心最终答案的第 k 位你完全可以把每个数的高位全部丢掉只保留第 k 位问题就退化成了一个只有 0 和 1 的数组上的计数问题。这个性质对“与”和“或”同样成立。与运算的第 k 位等于所有数第 k 位相与或运算的第 k 位等于所有数第 k 位相或。正因为如此我们才能把原本 O(2^n) 级别的子集枚举问题压缩成对每个位做一次 O(n) 或 O(log n) 的统计再乘以对应的位权 2^k 累加。注意按位独立的前提是运算本身在位上不产生跨位影响。异或、与、或都满足但加法和乘法不满足进位会跨位所以这套方法不能乱用。2.3 整体方案选型枚举位 组合计数确定按位处理后整体框架就很清晰了枚举每一个二进制位 k从 0 到最高位通常 30 或 60取决于数据范围。统计数组中第 k 位为 1 的元素个数记为 cnt1为 0 的个数记为 cnt0 n - cnt1。在这一位上根据题目要求的运算类型计算所有合法选取方案中该位最终为 1 的方案数。把这个方案数乘以 2^k累加到答案中。第三步是整道题的分水岭。不同的运算对应不同的计数公式而组合数学就在这里登场。比如异或场景下某一位最终为 1 当且仅当选取的元素中该位为 1 的个数是奇数与场景下最终为 1 当且仅当选取的所有元素该位都是 1或场景下最终为 1 当且仅当至少有一个选取的元素该位是 1。2.4 复杂度分析与方案优势按位枚举的层数是 O(log V)V 是值域。每一层内部如果只是简单统计复杂度是 O(n)。整体就是 O(n log V)对于 n 在 10^5 级别、值域在 2^30 以内的数据这个复杂度完全可以接受。相比直接枚举所有子集的 O(2^n)这个方案的优势是碾压性的。而且它的代码实现非常规整外层循环枚举位内层做统计和公式计算不容易写错。唯一需要注意的是组合数预处理和取模运算的细节。3. 核心细节解析与实操要点3.1 组合数预处理阶乘与逆元这类题目几乎必然涉及组合数 C(n, m) 的计算而且通常要求对一个大质数取模常见的是 998244353 或 10^97。标准做法是预处理阶乘数组和阶乘逆元数组const int MOD 998244353; const int MAXN 100005; long long fac[MAXN], inv_fac[MAXN]; long long power(long long base, long long exp) { long long res 1; while (exp) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } void init() { fac[0] 1; for (int i 1; i MAXN; i) fac[i] fac[i-1] * i % MOD; inv_fac[MAXN-1] power(fac[MAXN-1], MOD-2); for (int i MAXN-2; i 0; i--) inv_fac[i] inv_fac[i1] * (i1) % MOD; } long long C(int n, int m) { if (m 0 || m n) return 0; return fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD; }这段代码是模板级别的但有几个细节容易翻车。第一MAXN 要开够至少比 n 的最大值大 5 到 10。第二逆元用费马小定理求前提是 MOD 是质数这一点要确认题目给的模数确实是质数。第三fac 和 inv_fac 要用 long long中间乘法会爆 int。3.2 异或场景下的奇数计数公式假设当前位有 cnt1 个 1、cnt0 个 0。我们要统计有多少种选取方案使得选出的元素中 1 的个数为奇数。选取方案通常有两种理解一种是选取任意非空子集另一种是选取固定大小的子集。这里以“选取任意非空子集”为例。从 cnt1 个 1 中选奇数个从 cnt0 个 0 中选任意个。方案数为sum_{j 为奇数} C(cnt1, j) * 2^{cnt0}而 sum_{j 为奇数} C(cnt1, j) 有一个经典结论当 cnt1 1 时它等于 2^{cnt1 - 1}当 cnt1 0 时它等于 0。所以这一位的贡献方案数就是cnt1 12^{cnt1 - 1} * 2^{cnt0} 2^{n - 1}cnt1 00这个结论非常漂亮意味着异或场景下每一位的贡献只取决于这一位是否存在至少一个 1。如果存在贡献就是 2^{n-1}如果全是 0贡献就是 0。实操心得这个 2^{n-1} 的结论我一开始没反应过来硬推了一遍组合恒等式才确认。建议自己动手用二项式定理推一遍(1-1)^{cnt1} sum C(cnt1,j)*(-1)^j奇数项和偶数项之差为 0结合总和为 2^{cnt1}就能解出奇数项和为 2^{cnt1-1}。3.3 与运算和或运算的计数差异与运算场景下某一位最终为 1 要求选取的所有元素该位都是 1。如果选取的是任意非空子集那么方案数就是从 cnt1 个 1 中选任意非空子集即 2^{cnt1} - 1。如果 cnt1 0方案数为 0。或运算场景下某一位最终为 1 要求至少选一个该位为 1 的元素。方案数是从 cnt1 个 1 中选至少一个从 cnt0 个 0 中选任意个即 (2^{cnt1} - 1) * 2^{cnt0}。把三种运算的公式列成表格对比会更清楚运算类型该位最终为 1 的条件方案数任意非空子集异或选出的 1 的个数为奇数cnt1 1 时为 2^{n-1}否则 0与选出的元素全部为 12^{cnt1} - 1或至少选出一个 1(2^{cnt1} - 1) * 2^{cnt0}这张表是整道题的核心。你在写代码之前一定要先确认题目要求的到底是哪种运算以及选取方案是否允许空集。空集的处理会直接影响公式里的减一操作。3.4 取模与幂次预处理的注意事项2 的幂次在公式里反复出现建议提前预处理 pow2 数组pow2[0] 1; for (int i 1; i n; i) pow2[i] pow2[i-1] * 2 % MOD;这样每次用到 2^k 都是 O(1) 查询。注意 pow2 的下标要开到 n因为 2^{n-1} 和 2^{cnt0} 都可能用到 n 级别的指数。另外减法取模要记得加 MOD 再取模避免出现负数。比如 (pow2[cnt1] - 1 MOD) % MOD 这种写法要养成习惯。4. 完整实操过程与核心环节实现4.1 输入处理与最高位确定先把数组读进来同时确定最高位是多少。可以用一个变量 mx 记录所有数的或值然后看 mx 的最高有效位int n; cin n; vectorint a(n); int mx 0; for (int i 0; i n; i) { cin a[i]; mx | a[i]; } int max_bit 0; while ((1 max_bit) mx) max_bit;max_bit 就是我们需要枚举的位数上限。如果 mx 是 0max_bit 保持 0循环不会执行答案自然是 0。4.2 逐位统计与贡献累加核心循环长这样long long ans 0; for (int k 0; k max_bit; k) { int cnt1 0; for (int i 0; i n; i) { if ((a[i] k) 1) cnt1; } int cnt0 n - cnt1; long long ways 0; // 以异或为例 if (cnt1 1) { ways pow2[n-1]; } ans (ans ways * pow2[k]) % MOD; } cout ans endl;这段代码的结构非常清晰外层枚举位内层统计 cnt1然后套公式算 ways最后乘上位权累加。如果你写的是与运算或或运算只需要替换 ways 的计算部分。4.3 一个具体算例的手动推演假设 n 3数组是 [1, 2, 3]我们按异或场景来算。二进制展开1 012 103 11。最高位是第 1 位从 0 开始计数。第 0 位1、2、3 的第 0 位分别是 1、0、1cnt1 2cnt0 1。cnt1 1ways 2^{3-1} 4。贡献 4 * 2^0 4。第 1 位分别是 0、1、1cnt1 2cnt0 1。ways 4。贡献 4 * 2^1 8。总答案 4 8 12。我们可以暴力验证一下。所有非空子集{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}。异或和分别是 1, 2, 3, 3, 2, 1, 0。求和 1233210 12。对上了。这个手动推演的过程建议每个初学者都做一遍能帮你确认公式和代码是否一致。4.4 边界情况处理清单有几类边界情况必须单独确认n 1 时pow2[n-1] pow2[0] 1公式仍然成立。数组全为 0 时mx 0max_bit 0循环不执行答案 0。cnt1 0 的位异或场景 ways 0与场景 ways 0或场景 ways 0都不贡献。模数运算中减法要加 MOD。pow2 数组要开到 n不能只开到 max_bit。提示如果你在本地测试时答案总是差一点优先检查 pow2 数组有没有开够以及减法取模有没有处理负数。5. 常见问题与排查技巧实录5.1 答案偏小或偏大的典型原因最常见的问题是 pow2 数组开小了。比如 n 100000你只开了 100 的数组后面访问 pow2[n-1] 就会越界或者读到垃圾值。这类问题在本地小数据上不一定暴露一交上去就 WA。第二个常见原因是取模遗漏。ways * pow2[k] 这一步如果忘了取模long long 也会溢出。养成每一步乘法后都取模的习惯。第三个原因是把“非空子集”和“任意子集”搞混了。如果题目允许空集异或场景下 cnt1 1 时 ways 仍然是 2^{n-1}因为空集异或为 0不影响奇数计数但与运算场景下 ways 要变成 2^{cnt1} 而不是 2^{cnt1} - 1。这个差异一定要看清楚题面。5.2 组合数预处理报错的排查如果用了阶乘逆元预处理常见报错是数组越界或者逆元算错。检查这几点MAXN 是否大于 n 的最大值。power 函数的指数是否用了 MOD-2。inv_fac 的递推方向是否从大到小。C 函数里是否处理了 m 0 或 m n 的情况。5.3 常见问题速查表问题现象可能原因排查方法答案偏小pow2 数组开小检查数组大小是否 n1答案偏大取模遗漏每步乘法后检查 % MOD结果负数减法未加 MOD改成 (x - 1 MOD) % MOD小数据对大数据错溢出确认中间变量用 long long空集处理错误公式减一用错重新确认题面是否允许空集最高位漏算max_bit 计算错误用 mx 的二进制长度确认5.4 独家避坑技巧我在写这类题时有一个习惯先把小数据暴力跑一遍把暴力结果和公式结果对拍。n 15 的时候暴力枚举所有子集完全可行写一个 brute force 函数随机生成数组对比两个答案。这个方法帮我抓出过好几次公式推错的问题。另一个技巧是把每一位的 cnt1、cnt0、ways 都打印出来和手动推演的结果对比。尤其是第一次写的时候不要嫌麻烦打印一遍能省下大量调试时间。还有一个细节如果题目给的数据范围里 n 可能达到 10^6那么 O(n log V) 的常数就很重要了。内层统计 cnt1 的循环可以用位运算优化但通常没必要因为 log V 只有 30 左右总操作数在 3 * 10^7 级别C 完全跑得动。如果是 Python可能需要考虑用 numpy 或者换思路。6. 从这道题延伸出的通用解题框架6.1 位运算贡献法的适用边界这套“按位拆解 组合计数”的方法适用范围其实比这道题更广。凡是满足以下条件的题目都可以尝试运算是逐位独立的异或、与、或、同或等。需要统计所有子集或所有选取方案的某种聚合值。值域在 2^60 以内位数可控。不适用的情况也很明确涉及进位、借位的运算加法、乘法、减法或者位与位之间存在依赖关系的场景。6.2 组合恒等式的积累建议这道题用到的核心恒等式是“奇数项二项式系数之和等于 2^{n-1}”。类似的恒等式还有不少比如sum C(n, k) 2^nsum C(n, k) * k n * 2^{n-1}sum C(n, k)^2 C(2n, n)平时多积累这类恒等式遇到组合计数题时能快速反应。我自己的做法是整理一个笔记每遇到一个新恒等式就记下来附上推导过程和一个应用例子。6.3 代码模板的复用与调整阶乘逆元预处理、快速幂、按位枚举这三块代码在大量题目里都能直接复用。建议把它们整理成个人模板比赛时直接粘贴。但要注意模板里的 MAXN 和 MOD 要根据题目调整不能无脑照搬。我在实际比赛中的体会是这类题目的代码量不大难点全在思路和公式推导上。一旦想清楚了按位独立的性质和对应的计数公式剩下的就是十分钟的编码工作。真正拉开差距的是你能不能在读完题之后迅速识别出“这是按位贡献法”的信号。这个识别能力只能靠多做题、多总结来培养。
阅读完成 · 觉得有帮助？
