Moe's CF Life

Appearance

喵~ Jzzhu 和他的数字们，一个关于位运算与容斥的魔法✨ ​

哈喽，各位算法大师们，喵~ 今天咱家要和大家分享一道非常有趣的题目，来自 Codeforces 的 449D - Jzzhu and Numbers。这道题完美地将位运算、容斥原理和一种叫做“高维前缀和”（或者叫 SOS DP）的酷炫技巧结合在了一起。

准备好了吗？那就跟着咱家的爪爪，一步步揭开这道题的神秘面纱吧！🐾

题目大意 ​

Jzzhu 有 n 个非负整数 a1, a2, ..., an。他想知道，有多少个由这些数字的下标组成的非空子序列 i1, i2, ..., ik (这里要求 1 <= i1 < i2 < ... < ik <= n)，满足这些下标对应的数字的按位与（Bitwise AND）结果为 0？

也就是说，我们要找有多少个非空子集，它们的元素的 & 运算结果是 0。

比如说，如果数字是 [2, 3, 3]。

  • 子集 {2}: AND 结果是 2
  • 子集 {3}: AND 结果是 3
  • 子集 {3}: AND 结果是 3
  • 子集 {2, 3}: 2 & 3 = (10)_2 & (11)_2 = (10)_2 = 2
  • 子集 {2, 3}: 2 & 3 = 2
  • 子集 {3, 3}: 3 & 3 = 3
  • 子集 {2, 3, 3}: 2 & 3 & 3 = 2 没有一个子集的 AND 和是 0，所以答案是 0。

再比如，如果数字是 [0, 1, 2, 3]。

  • 任何包含 0 的子集，它们的 AND 和一定是 0。
    • {0}
    • {0, 1}
    • {0, 2}
    • {0, 3}
    • {0, 1, 2}
    • {0, 1, 3}
    • {0, 2, 3}
    • {0, 1, 2, 3}
    • 这里就有 2^(4-1) = 8 个了。
  • 不包含 0 的子集：
    • {1, 2}: 1 & 2 = 0。这是一个。
    • {1, 2, 3}: 1 & 2 & 3 = 0。这又是一个。 所以总共有 8 + 1 + 1 = 10 个。

题目要求我们输出这个数量，并对 10^9 + 7 取模。

解题方法 ​

直接去数 AND 和为 0 的子集数量，感觉有点像无头苍蝇，喵~ 因为限制条件 ... = 0 太宽泛了。一个数的某一位是 0，就能让最终结果的这一位变成 0。

这时候，咱家的小脑袋瓜灵光一闪！正着不好算，咱就反着来嘛！

容斥原理登场！

我们可以换一个角度思考：

  • 设 f(mask) 表示 AND 和是 mask 的超集 的子集有多少个。
    • “A 是 B 的超集” 在位运算里是什么意思呢？就是 A & B == B。也就是说，B 中为 1 的位，在 A 中也必须为 1。
  • 那么，f(mask) 就是由 所有是 mask 的超集的那些输入数字 a_i 组成的非空子集的数量。
  • 假设在输入中有 k 个数字都是 mask 的超集，那么由它们能组成的非空子集就有 2^k - 1 个。所以 f(mask) = 2^k - 1。

但是我们想求的是 AND 和恰好等于 0 的子集数量。这就要用到容斥原理了。

令 g(mask) 表示 AND 和恰好为 mask 的子集数量。我们想求的就是 g(0)。 根据容斥原理（或者说是子集反演），我们有： g(0) = f(0) - (f(1) + f(2) + f(4) + ...) + (f(3) + f(5) + f(6) + ...) - ...

用更优雅的数学语言来说就是： g(0) = Σ (-1)^popcount(mask) * f(mask) （这里的 popcount(mask) 是 mask 二进制表示中 1 的个数）

不过，f(mask) = 2^k - 1 带着一个 -1，处理起来有点麻烦。咱们可以稍微变通一下。

设 F(mask) 表示 AND 和是 mask 的超集 的子集有多少个（这次我们把空集也算上！）。 如果输入中有 cnt[mask] 个数字是 mask 的超集，那么 F(mask) = 2^cnt[mask]。

同样通过容斥原理，我们可以得到 AND 和恰好为 0 的子集数量： ans = Σ (mask from 0 to MAX_VAL-1) (-1)^popcount(mask) * F(mask)ans = Σ (mask from 0 to MAX_VAL-1) (-1)^popcount(mask) * 2^cnt[mask]

这个公式看起来就很清爽了，喵~

现在问题来了，怎么快速计算 cnt[mask] 呢？ cnt[mask] 表示输入 a 中，有多少个 a_i 满足 a_i & mask == mask。 如果我们对每个 mask 都遍历一遍 n 个数字，那复杂度就是 O(n * MAX_VAL)，太慢了！

高维前缀和（SOS DP）来救驾！

这个技巧也叫“Sum over Supermasks”或者“高维后缀和”。

  1. 首先，我们用一个数组 dp 统计输入中每个数字出现的次数。dp[x] 就是数字 x 的出现次数。
  2. 我们想计算的 cnt[mask] 其实是 Σ dp[x]，其中 x 是 mask 的所有超集。
  3. 我们可以用一个 DP 来实现这个“后缀和”的计算。
    cpp
    // dp[mask] 初始化为数字 mask 的出现次数
for (int i = 0; i < BITS; ++i) { // 遍历所有位
    for (int mask = 0; mask < MAX_VAL; ++mask) {
        // 如果 mask 的第 i 位是 1
        if (mask & (1 << i)) {
            // 那么 mask 的所有超集，也是 (mask 去掉第 i 位) 这个数的所有超集的一部分
            // 所以把 mask 的计数，加到 (mask 去掉第 i 位) 的计数上
            dp[mask ^ (1 << i)] += dp[mask];
        }
    }
}
    这个 DP 的过程是从高位到低位（或者说从大 mask 到小 mask）累加。完成之后，dp[mask] 就变成了我们想要的 cnt[mask] 了！它的复杂度是 O(BITS * 2^BITS)，非常快。

最终算法步骤

  1. 初始化一个频率数组 counts，counts[x] 记录数字 x 在输入中出现的次数。
  2. 使用高维后缀和 DP（如上所述）来更新 counts 数组。之后，counts[mask] 就存储了输入中有多少个数是 mask 的超集。
  3. 预计算 2 的幂次，p2[i] = 2^i % MOD。
  4. 初始化答案 ans = 0。
  5. 遍历从 0 到 MAX_VAL-1 的所有 mask：
    • 计算 term = p2[counts[mask]]。
    • 如果 popcount(mask) 是奇数，就从 ans 中减去 term。
    • 如果 popcount(mask) 是偶数，就给 ans 加上 term。
    • 记得每次运算都取模，并且减法要 (ans - term + MOD) % MOD 防止负数哦。
  6. 最后得到的 ans 就是我们的答案啦！

题解代码 (C++) ​

这是咱家整理好的代码，加了一些注释方便理解，喵~

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 用一个宏来处理不同编译器下的 popcount 内置函数，很方便的小技巧喵~
#if defined(__GNUC__) || defined(__clang__)
#define BUILTIN_POPCOUNT __builtin_popcount
#else
#include <intrin.h>
#define BUILTIN_POPCOUNT __popcnt
#endif

void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

const int MOD = 1000000007;
const int BITS = 20; // 题目中 a_i <= 10^6，小于 2^20，所以 20 位就够了
const int MAX_VAL = 1 << BITS;

int main() {
    fast_io();
    int n;
    std::cin >> n;

    // 1. 统计每个数字出现的次数
    std::vector<int> counts(MAX_VAL, 0);
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        counts[a]++;
    }

    // 2. 高维后缀和 (Sum over Supermasks DP)
    // 计算 cnt[mask]：输入中有多少个数是 mask 的超集
    // 这个循环结束后，counts[mask] 的含义就变了哦！
    for (int i = 0; i < BITS; ++i) {
        for (int mask = 0; mask < MAX_VAL; ++mask) {
            // 我们从包含第 i 位的 mask，把它的数量加给不包含第 i 位的 mask
            // 这样从高位到低位迭代，就能正确算出超集和
            if (mask & (1 << i)) {
                counts[mask ^ (1 << i)] += counts[mask];
            }
        }
    }

    // 3. 预计算 2 的幂
    std::vector<long long> p2(n + 1);
    p2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p2[i] = (p2[i - 1] * 2) % MOD;
    }

    // 4. 使用容斥原理计算最终答案
    long long ans = 0;
    for (int mask = 0; mask < MAX_VAL; ++mask) {
        // F(mask) = 2^cnt[mask]
        long long term = p2[counts[mask]];
        
        // 根据 popcount 的奇偶性来决定是加还是减，这就是 (-1)^popcount(mask)
        if (BUILTIN_POPCOUNT(mask) % 2 == 1) {
            ans = (ans - term + MOD) % MOD; // 减法要小心负数
        } else {
            ans = (ans + term) % MOD;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

知识点介绍 ​

这道题用到的知识点都非常经典，掌握了它们，就能解决一大类位运算相关的计数问题呢！

  1. 位运算 (Bitwise Operations)

    • 核心是 & (按位与) 运算。A & B 的结果中，只有在 A 和 B 中都为 1 的位，结果才为 1，否则为 0。
    • A 是 B 的超集 (A is a supermask of B)，等价于 A & B == B。
    • A 是 B 的子集 (A is a submask of B)，等价于 A & B == A。

  2. 容斥原理 (Inclusion-Exclusion Principle)

    • 这是一个强大的组合计数工具。最简单的形式是 |A ∪ B| = |A| + |B| - |A ∩ B|。
    • 在题目中，我们用它来处理“恰好”等于某个值的问题。我们先计算“至少”满足某些属性（是某个 mask 的超集）的数量，然后通过加加减减来得到“恰好”满足无属性（mask=0）的数量。
    • 公式 ans = Σ (-1)^popcount(mask) * F(mask) 是容斥原理在子集问题上的经典应用，也叫“子集反演”或“莫比乌斯反演”。

  3. 高维前缀/后缀和 (SOS DP / High-Dimensional Prefix/Suffix Sums)

    • 这是一种在 O(D * 2^D) 时间内计算所有子集或超集信息的动态规划技巧（D 是位数）。
    • 高维前缀和 (Sum over Submasks)：计算 dp[mask] = Σ f[submask]，其中 submask 是 mask 的子集。
    • 高维后缀和 (Sum over Supermasks)：计算 dp[mask] = Σ f[supermask]，其中 supermask 是 mask 的超集。本题用的就是这种。
    • 它们也被称为 快速沃尔什-阿达玛变换 (Fast Walsh-Hadamard Transform, FWHT) 的一部分，专门用于处理位运算卷积（AND, OR, XOR）。本题的计算过程，本质上就是对频率数组做了一个 AND 卷积的变换。

好啦，今天的题解分享就到这里啦！希望大家能有所收获，喵~ 如果有任何问题，欢迎随时来找咱家讨论哦！下次再见！💖

Released under the MIT License.

Copyright © 2024-present Moe