H. Don't Blame Me - 题解

比赛与标签

比赛: Codeforces Round 871 (Div. 4) 标签: bitmasks, combinatorics, dp, math 难度: *1700

喵喵，这是什么任务呀？

主人，你好呀~ 这道题是让咱们在一个正整数数组 a 中，找出所有非空的子序列，要求子序列里所有元素的按位与（Bitwise AND）结果，它的二进制表示中恰好有 k 个 1。最后把这样的子序列总数告诉人家，记得要对 10^9+7 取模哦，喵~

举个例子，如果数组是 [5, 5, 7, 4, 2]，k=1。

子序列 [5] 的按位与结果是 5 (二进制 101)，有2个1，不满足。
子序列 [4] 的按位与结果是 4 (二进制 100)，有1个1，满足！
子序列 [5, 4] 的按位与结果是 5 & 4 = 4 (二进制 101 & 100 = 100)，有1个1，也满足！

咱们的任务就是数清楚所有满足条件的子序列有多少个，的说。

跟着本喵的思路来喵！

这个问题如果直接去枚举所有 2^n - 1 个非空子序列，那肯定会超时的啦，n 最大有 20 万呢！所以我们需要更聪明的办法，喵~

注意到题目给的 a[i] 的值都非常小，最大只有 63。这是一个非常重要的提示！63 的二进制是 111111，也就是说所有数字都可以在 6 个比特位内表示。这强烈地暗示咱们可以使用 位运算 和 动态规划 (DP) 来解决，呐。

咱们来设计一个 DP 吧！

1. DP 状态定义

我们需要记录的是，当我们遍历数组时，已经形成的子序列的按位与结果是什么。所以，我们可以定义一个状态： dp[mask] 表示：从已经考虑过的数字中，能够构成多少个子序列，使得这些子序列中所有元素的按位与结果恰好为 mask。

这里的 mask 就是一个 0 到 63 之间的整数，代表一个位掩码。

2. DP 初始化

在开始遍历数组 a 之前，我们什么数字都还没选。可以认为我们有一个“初始状态”，这个状态再与任何数 x 进行 AND 操作，结果都会是 x。在位运算中，满足这个性质的“单位元”是什么呢？对于 AND 操作，是所有位都为 1 的数！因为 x & 111...1 = x。由于 a[i] <= 63，我们只需要考虑 6 个比特位，所以这个“单位元”就是 63 (二进制 111111)。

所以，我们可以初始化 dp[63] = 1，代表一个“空选择”的状态。所有其他的 dp[mask] 都初始化为 0。这个 dp[63]=1 就像一个魔法种子，之后所有的子序列都是从它生长出来的喵~

3. DP 状态转移

现在，我们从左到右遍历数组 a 中的每一个数字 a[i]。对于每个 a[i]，它可以被加入到任何一个我们已经形成的子序列中，也可以不加入。

我们来考虑 a[i] 对 dp 数组的影响：对于每一个已有的 mask（0 <= mask <= 63），dp[mask] 记录了按位与结果为 mask 的子序列数量。

选择不加入 a[i]：原来的 dp[mask] 个子序列保持不变。它们的按位与结果仍然是 mask。
选择加入 a[i]：对于原来的 dp[mask] 个子序列，我们把 a[i] 添加进去，形成 dp[mask] 个新的子序列。这些新子序列的按位与结果会变成 mask & a[i]。

所以，当我们处理完 a[i] 后，新的 dp 状态 new_dp 会这样更新： new_dp[mask] 的值，一部分来自于原来结果就是 mask 的子序列（不加 a[i]），另一部分来自于原来结果是 old_mask，但 old_mask & a[i] == mask 的子序列（加上 a[i]）。

一个更清晰的转移方式是：遍历数组 a 中的每个元素 x。创建一个新的 new_dp 数组，先让它等于当前的 dp 数组（这代表了所有不选择 x 的情况）。然后，遍历所有 mask（从 0 到 63），如果 dp[mask] 不为 0，说明存在按位与为 mask 的子序列。我们将 x 加入这些子序列，得到的新按位与结果是 new_mask = mask & x。所以，我们让 new_dp[new_mask] 加上 dp[mask]。 new_dp[new_mask] = (new_dp[new_mask] + dp[mask]) % mod 完成所有 mask 的更新后，令 dp = new_dp，然后继续处理下一个元素。

4. 处理非空子序列

题目要求的是非空子序列。我们的 dp[63] = 1 初始化代表的是一个“空选择”，它本身对应的是空集。在整个 DP 过程中，这个 1 会一直被传递。如果一个子序列的按位与结果恰好是 63，那么它也会被计入 dp[63]。所以，在所有计算结束后，dp[63] 的值包含了“空选择”的那 1 个，以及所有非空且按位与结果为 63 的子序列。因此，我们需要从最终的 dp[63] 中减去 1。对于其他的 mask < 63，dp[mask] 里的计数一定都来自非空子序列，因为要得到一个小于 63 的结果，至少要与一个数进行 AND 操作，所以不需要处理。

5. 计算最终答案

遍历完整个数组 a 后，dp[mask] 就存储了所有非空子序列按位与结果为 mask 的数量。我们只需要遍历从 0 到 63 的所有 mask，如果一个 mask 的二进制表示中 1 的个数等于 k，就把 dp[mask] 加入到最终答案 ans 中。为了快速判断 1 的个数，我们可以预处理或者使用内置函数 __builtin_popcount()，非常方便的喵！

把思路变成魔法代码喵！

cpp

#include <iostream>
#include <vector>
#include <numeric> // 虽然这个代码里没用到，但是是个好习惯喵~

using namespace std;

// 定义模数，可不能忘了它哦
const long long mod = 1000000007;

int main() {
    // 加速输入输出，让程序跑得飞快~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理 0 到 63 每个数字的二进制中 1 的个数
    int bit_count[64];
    for (int i = 0; i < 64; i++) {
        // __builtin_popcount 是个神奇的函数，能直接数出1的个数！
        bit_count[i] = __builtin_popcount(i);
    }

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // dp[mask] 表示按位与结果为 mask 的子序列数量
        vector<long long> dp(64, 0);
        
        // 初始化，dp[63] = 1 代表一个“空选择”的初始状态
        // 63 的二进制是 111111，是按位与的单位元
        dp[63] = 1;

        // 遍历数组中的每一个元素
        for (int i = 0; i < n; i++) {
            vector<long long> new_dp = dp; // 复制一份，代表不选择 a[i] 的情况
            // 遍历所有可能的 mask
            for (int mask = 0; mask < 64; mask++) {
                // 对于 dp[mask] 个子序列，我们都可以选择加上 a[i]
                int new_mask = mask & a[i];
                // 那么就会产生 dp[mask] 个新的子序列，其按位与结果为 new_mask
                new_dp[new_mask] = (new_dp[new_mask] + dp[mask]) % mod;
            }
            // 更新 dp 数组为处理完 a[i] 之后的状态
            dp = new_dp;
        }

        // 题目要求非空子序列
        // 我们初始化的 dp[63]=1 是为空集准备的，所以要减掉它
        dp[63] = (dp[63] - 1 + mod) % mod;

        long long ans = 0;
        // 遍历所有可能的按位与结果
        for (int mask = 0; mask < 64; mask++) {
            // 如果这个结果的二进制中 1 的数量正好是 k
            if (bit_count[mask] == k) {
                // 就把对应的子序列数量加到答案里
                ans = (ans + dp[mask]) % mod;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

分析一下我们的魔法有多快喵~

时间复杂度: O(N * 64) 的说。对于每个测试用例，我们需要遍历长度为 N 的数组 a。在处理每个元素 a[i] 时，我们都需要遍历一遍 dp 数组，dp 数组的大小是 64。所以总的时间复杂度是 O(N * 64)。由于所有测试用例的 N 的总和有上限，这个复杂度是完全可以接受的！
空间复杂度: O(64) 的说。我们主要使用了 dp 和 new_dp 两个数组，它们的大小都是固定的 64。所以空间复杂度是 O(1) 的常数级别，非常优秀！

这次探险的宝藏喵！

这次解题，我们又收集到了一些闪闪发光的知识点呢，喵~

DP on Bitmasks (位DP): 这是解决与位运算相关的组合计数问题的强大武器。当问题状态可以用一个小的整数（位掩码）来表示时，就可以考虑使用这种 DP。
DP的初始化技巧: 对于涉及某种运算（如AND, OR, XOR, 加法）的DP，找到其对应的“单位元”来初始化空集或初始状态，是一个非常常见的技巧。比如AND的单位元是全1，OR/XOR的单位元是0。
识别问题特征: 看到数值范围很小（比如 a[i] <= 63），就要立刻变得警觉起来！这通常是使用位运算、状压DP或相关技巧的强烈信号。
处理细节: 一定要仔细阅读题目要求，比如“非空子序列”。这种细节常常是陷阱，就像藏在毛线球里的小刺，一不小心就会被扎到。我们通过在最后修正 dp[63] 的值，完美地解决了这个问题，喵~

希望这篇题解能帮到主人哦！如果还有其他问题，随时可以再来找本喵玩，的说！>w<

H. Don't Blame Me - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ ​

跟着本喵的思路来喵！ ​

1. DP 状态定义 ​

2. DP 初始化 ​

3. DP 状态转移 ​

4. 处理非空子序列 ​

5. 计算最终答案 ​

把思路变成魔法代码喵！ ​

分析一下我们的魔法有多快喵~ ​

这次探险的宝藏喵！ ​