193 小 K 的区间与值和

问题描述

小 K 有一个长度为 n 的数组 a，她定义数组的权值为数组中任意两个数按位与（bitwise AND）的值之和。具体来说，对于数组中的每个连续子数组，我们可以计算所有可能的两个元素的按位与值之和，并将这些值相加。小 K 想知道该数组中所有可能的连续子数组的权值和是多少，最后结果对 $10^9 + 7$ 取模。

解题思路

为了高效地计算所有连续子数组的权值和，我们需要找到一种方法避免枚举所有可能的子数组和其中的元素对。这可以通过逐位考虑每一位的贡献来实现。

具体步骤如下：

1. 逐位处理：对于每一位 i（从第 0 位到第 31 位），计算该位在所有连续子数组中的贡献总和。

2. 统计位为 1 的情况：在数组中，如果某个元素的第 i 位为 1，那么它可以与之前位为 1 的元素形成按位与为 1 << i 的对。

3. 计算子数组数量：对于 nums[j] 的每一位，考虑每个 pair(i, j) 满足 nums[i] & nums[j] = 1，包含 nums[i:j] 的连续子数组左端点选择范围为 [0 - i]，右端点 [j, n - 1]，一共 (i + 1) * (n - j) 个。对于当前位置 j，我们可以统计出满足条件的 i 的个数累加起来，那么对于当前位置 j，满足条件的子数组个数为 cnt * (n - j)。

代码实现

mod = int(1e9 + 7)

def solution(n: int, a: list) -> int:
    res = 0
    for i in range(32):
        cnt = 0
        for j in range(n):
            if a[j] >> i & 1:      # 当前位是1
                res += cnt * (n - j) * (1 << i)
                res %= mod
                cnt += j + 1  # 统计满足条件的i的个数
    return res

if __name__ == '__main__':
    print(solution(4, [2, 3, 1, 2]) == 16)
    print(solution(3, [5, 6, 7]) == 25)
    print(solution(2, [1, 10]) == 0)
    print(solution(5, [1, 2, 4, 8, 16]) == 0)