统计数组中满足异或和与X按位与等于0的子序列数量

问题描述 #

给定一个由整数组成的数组，统计满足以下条件的子序列数量：

• 设 i1, i2, i3...ik 为给定数组的下标，Ai1, Ai2, Ai3....Aik 为对应的元素，X 为给定整数，N 为数组长度，A 为输入数组
• 统计所有满足 (Ai1 ^ Ai2 ^ Ai3 ^ ... ^ Aik) & X == 0 的子序列，空数组视为合法子序列

输入样例说明 #

A = [5,3,7], N = 3, X = 1
总共有2^3=8个子序列，最终符合条件的子序列数量为4。

解题思路 #

1. 条件等价转换：(异或和) & X == 0 本质要求异或和在所有X为1的二进制位上取值都为0，其余位不影响判断。我们可以将每个元素和X做按位与，只保留X为1的位，问题直接转换为：统计异或结果为0的子序列数量。
2. 线性基求解：用线性基统计数组中线性无关的元素个数r，满足异或和为0的子序列总数为2^(N - r)。原理是线性无关的r个元素可以组合出所有可能的异或结果，剩下的N-r个元素每个都可以自由选择是否选取，总能找到对应的线性基组合使得总异或和为0。

完整代码实现 #

public long count(int[] A, int N, int X){
    // 适配Java 32位int的线性基
    int[] base = new int[32];
    int r = 0;
    for (int num : A) {
        // 仅保留X为1的位，过滤不影响判断的位
        int mask = num & X;
        if (mask == 0) {
            // 掩码为0的元素无法插入线性基，直接跳过
            continue;
        }
        int cur = mask;
        for (int i = 31; i >= 0; i--) {
            if (((cur >> i) & 1) == 1) {
                if (base[i] == 0) {
                    base[i] = cur;
                    r++;
                    break;
                } else {
                    cur ^= base[i];
                }
            }
        }
    }
    // 计算2的(N - r)次方，用long避免溢出
    return 1L << (N - r);
}

样例验证 #

对于样例A = [5,3,7], X=1：

• 每个元素的掩码分别为5&1=1、3&1=1、7&1=1
• 线性基最终仅插入1个有效元素，r=1
• 结果为2^(3-1) = 4，和预期结果一致。

内容的提问来源于stack exchange，提问作者Bal Vikash Sharma