求给定数组所有大小≥2的子集的最大最小元素按位或之和

首先，暴力枚举所有子集显然不可行——数组规模是1e5级，子集数量是指数级的，根本跑不完。我们需要用按位贡献+排序预处理的思路，利用二进制位的独立性和容斥原理来高效计算。

核心思路 #

按位或的每一位是独立的，我们可以计算每个二进制位k在最终总和中的贡献：即有多少个符合条件的子集（大小≥2），使得该子集的max|min的第k位为1，然后用这个数量乘以2^k，最后把所有位的贡献加起来就是答案。

根据按位或的性质，max|min的第k位为1等价于：max的第k位是1 或者 min的第k位是1。我们用容斥原理拆分这个条件：

符合条件的子集数 = （max第k位为1的子集数） + （min第k位为1的子集数） - （max和min第k位都为1的子集数）

具体步骤 #

1. 排序数组：排序后可以方便地计算以每个元素为max或min的子集数量。
2. 预处理2的幂次数组：提前计算pow2[i] = 2^i，因为我们需要频繁用到选子集的数量。
3. 遍历每一位二进制位（通常0到30，因为int型数的有效位最多31位）：
   • 计算A：所有大小≥2、max的第k位为1的子集数。对于排序后的数组中第i个元素，如果它的第k位是1，那么以它为max的符合条件的子集数是pow2[i] - 1（左边i个元素选任意非空子集，加上它自己，子集大小≥2）。
   • 计算B：所有大小≥2、min的第k位为1的子集数。对于排序后的数组中第j个元素，如果它的第k位是1，那么以它为min的符合条件的子集数是pow2[n-1-j] - 1（右边n-1-j个元素选任意非空子集，加上它自己，子集大小≥2）。
   • 计算C：所有大小≥2、max和min第k位都为1的子集数。这等价于所有元素第k位都为1的大小≥2的子集数，假设数组中有cnt个元素第k位为1，那么C = pow2[cnt] - cnt - 1。
   • 计算该位贡献：(A + B - C) * (1 << k)，累加到总答案。

示例验证（数组[1,3,5]） #

排序后数组为[1,3,5]，n=3：

• 预处理pow2数组：[1,2,4,8]
• 位k=0（2^0=1）：
  • A：元素1（i=0）位0为1，但pow2[0]-1=0；元素3（i=1）位0为1，pow2[1]-1=1；元素5（i=2）位0为1，pow2[2]-1=3 → A=0+1+3=4
  • B：元素1（j=0）位0为1，pow2[3-1-0]-1=3；元素3（j=1）位0为1，pow2[3-1-1]-1=1；元素5（j=2）位0为1，pow2[3-1-2]-1=0 → B=3+1+0=4
  • cnt=3，C=8-3-1=4
  • 贡献：(4+4-4)*1=4
• 位k=1（2^1=2）：
  • A：只有元素3（i=1）位1为1，pow2[1]-1=1 → A=1
  • B：只有元素3（j=1）位1为1，pow2[3-1-1]-1=1 → B=1
  • cnt=1，C=2-1-1=0
  • 贡献：(1+1-0)*2=4
• 位k=2（2^2=4）：
  • A：只有元素5（i=2）位2为1，pow2[2]-1=3 → A=3
  • B：元素5（j=2）位2为1，pow2[3-1-2]-1=0 → B=0
  • cnt=1，C=2-1-1=0
  • 贡献：(3+0-0)*4=12
• 总答案：4+4+12=20，和示例一致。

Python代码实现 #

def calculate_sum(nums):
    nums.sort()
    n = len(nums)
    if n < 2:
        return 0
    
    # 预处理2的幂次，Python支持大整数，无需担心溢出
    pow2 = [1] * (n + 1)
    for i in range(1, n+1):
        pow2[i] = pow2[i-1] * 2
    
    total = 0
    for k in range(31):  # 处理0到30位
        A = 0
        B = 0
        cnt = 0
        for i in range(n):
            bit = (nums[i] >> k) & 1
            if bit:
                cnt += 1
                # 累加以当前元素为max的符合条件子集数
                A += pow2[i] - 1
                # 累加以当前元素为min的符合条件子集数
                B += pow2[n-1 - i] - 1
        # 计算max和min位k都为1的子集数
        C = pow2[cnt] - cnt - 1
        # 累加当前位的总贡献
        total += (A + B - C) * (1 << k)
    return total

# 测试示例
print(calculate_sum([1,3,5]))  # 输出20

时间复杂度分析 #

• 排序：O(n log n)
• 预处理幂次：O(n)
• 遍历每一位并计算A/B/C：O(31n)
  总时间复杂度为O(n log n)，完全适配1e5规模的数组。

内容的提问来源于stack exchange，提问作者Shewta