2026-04-11：有效子序列的数量。用go语言，给定一个整数数组 nums，定义“强度”为数组中所有元素做按位或运算（OR）的结果。你可以从原

福大大架构师每日一题

发布于 2026-04-14 16:29:49

190

2026-04-11：有效子序列的数量。用go语言，给定一个整数数组 nums，定义“强度”为数组中所有元素做按位或运算（OR）的结果。你可以从原数组中删去一些元素但保持剩余元素的相对顺序，得到一个非空子序列。若删除这个子序列后，剩余数组的强度相较原来变小（严格减少），则称这个子序列为“有效子序列”。要求统计数组中所有有效子序列的数量，并对结果取模 1000000007 返回。

备注：若剩余数组为空，其按位或结果为 0。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000。

输入： nums = [1,2,3]。

输出： 3。

解释：

数组的按位或为 1 OR 2 OR 3 = 3。

有效子序列为：

[1, 3]：剩余元素 [2] 的按位或为 2。

[2, 3]：剩余元素 [1] 的按位或为 1。

[1, 2, 3]：剩余元素 [] 的按位或为 0。

因此，有效子序列的总数为 3。

题目来自力扣3757。

一、整体解题步骤

步骤1：预处理基础数据

1. 预计算 2的幂次数组：因为长度为n的数组，总共有 2ⁿ 个子序列（包含空序列），题目要求取模 1e9+7，所以提前把 2⁰ ~ 2¹⁰⁰⁰⁰⁰ 全部计算好并取模，后续直接调用。
2. 计算原数组的总按位或 total_or：遍历所有元素，不断做按位或，得到整个数组的强度。
3. 快速优化判断：如果数组里所有数字都相同，直接得出结果（这种场景只有删除整个数组这1种有效情况）。

步骤2：位运算宽度计算

计算 total_or 的二进制有效位数 w：

• 比如 total_or=3（二进制 11），有效位数 w=2；
• 这个值决定了后续子集枚举的范围（总共有 2ʷ 个二进制子集）。

步骤3：高维前缀和（ SOS DP ）计算元素子集数量

这是核心步骤，目的是：统计数组中，每一个二进制子集 s 对应的元素个数（即数组里有多少个数字，它的二进制位是子集 s 的一部分）。

1. 初始化计数数组：先统计数组中每个数字出现的次数。
2. 按位填充计数：遍历 total_or 的每一个二进制位，对所有二进制子集进行更新，最终得到： f[s] = 数组中所有二进制位都包含在s里的元素总个数。简单说：f[s] 是能被 s 完全“覆盖”的元素数量。
3. 优化：只处理 total_or 中为1的二进制位，为0的位直接跳过，减少计算量。

步骤4：容斥原理计算无效子序列数量

无效子序列：删除后剩余元素的强度 = total_or。我们用容斥原理枚举 total_or 的所有子集，计算出所有无效子序列的数量。

1. 初始值：总子序列数量 = 2ⁿ（n是数组长度，包含空序列）。
2. 枚举 total_or 的所有子集：
- • 对每个子集，根据子集的二进制位数计算容斥系数（正负交替）。
- • 用预处理的2的幂次，结合 f[s] 计算该子集对应的子序列数量。
- • 用总数量减去/加上对应值，剔除所有无效子序列。
3. 核心逻辑：通过容斥，精准筛掉所有「删除后剩余强度不变」的无效子序列。

步骤5：结果修正与输出

1. 对计算结果取模 1e9+7。
2. 保证结果为非负数（模运算可能出现负数，加上模数再取模）。
3. 最终得到的就是有效子序列的总数。

二、以示例 nums=[1,2,3] 验证过程

1. 原数组强度：1|2|3=3（二进制11）。
2. 总非空子序列数：2³-1=7。
3. 无效子序列：删除后剩余强度仍为3的子序列，共4个。
4. 有效子序列 = 7 - 4 = 3（和题目输出一致）。

三、时间复杂度 & 额外空间复杂度

1. 时间复杂度

设：

• 数组长度：n（最大1e5）；
• total_or 的二进制有效位数：w（最大约20，因为元素≤1e6）。

总时间复杂度：O(n·w)

• 预处理2的幂次：O(1e5) 常数级；
• 计算总按位或：O(n)；
• SOS DP计算子集计数：O(n + w·2ʷ)；
• 容斥原理枚举子集：O(2ʷ)；
• 核心瓶颈：n·w，w是常数（≤20），因此整体是线性时间，能处理1e5的数组。

2. 额外空间复杂度

O(2ʷ)

• 预处理的幂次数组：固定大小1e5+1，常数级；
• 子集计数数组 f：大小为 2ʷ（≤1e6）；
• 其余变量都是常数级空间；
• 整体空间与数组长度n无关，仅由二进制位数决定，是极小的常数空间。

总结

1. 解题核心：反向思维（总-无效）+ SOS DP（子集统计）+ 容斥原理（筛除无效）；
2. 时间复杂度：O(n·w)（线性复杂度，适配1e5数据量）；
3. 额外空间复杂度：O(2ʷ)（极小的常数空间）。

Go完整代码如下：

package main

import (
    "fmt"
    "math/bits"
)

const mod = 1_000_000_007
const maxN = 100_001

var pow2 = [maxN]int{1}

func init() {
    // 预处理 2 的幂
    for i := 1; i < maxN; i++ {
        pow2[i] = pow2[i-1] * 2 % mod
    }
}

func countEffective(nums []int)int {
    or := 0
    same := true
    for _, x := range nums {
        or |= x
        if x != nums[0] {
            same = false
        }
    }
    // 优化：如果 nums 只有一种数字，那么非空子序列的按位或都是 or，只有空子序列的按位或比 or 小
    if same {
        return1
    }

    w := bits.Len(uint(or))
    f := make([]int, 1<<w)
    for _, x := range nums {
        f[x]++
    }
    for i := range w {
        if or>>i&1 == 0 { // 优化：or 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到，无需计算
            continue
        }
        for s := 0; s < 1<<w; s++ {
            s |= 1 << i
            f[s] += f[s^1<<i]
        }
    }
    // 计算完毕后，f[s] 表示 nums 中的是 s 的子集的元素个数

    ans := pow2[len(nums)] // 所有子序列的个数
    // 枚举 or 的所有子集（包括空集）
    for sub, ok := or, true; ok; ok = sub != or {
        sign := 1 - bits.OnesCount(uint(or^sub))%2*2
        ans -= sign * pow2[f[sub]]
        sub = (sub - 1) & or
    }
    return (ans%mod + mod) % mod // 保证结果非负
}

func main() {
    nums := []int{1, 2, 3}
    result := countEffective(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

MOD = 1_000_000_007
MAX_N = 100_001

# 预处理 2 的幂
pow2 = [1] * MAX_N
for i in range(1, MAX_N):
    pow2[i] = pow2[i-1] * 2 % MOD


def count_effective(nums: List[int]) -> int:
    or_val = 0
    same = True
    for x in nums:
        or_val |= x
        if x != nums[0]:
            same = False
    
    # 优化：如果 nums 只有一种数字，那么非空子序列的按位或都是 or_val，只有空子序列的按位或比 or_val 小
    if same:
        return1
    
    w = or_val.bit_length()
    f = [0] * (1 << w)
    for x in nums:
        f[x] += 1
    
    for i in range(w):
        if (or_val >> i) & 1 == 0:  # 优化：or_val 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到，无需计算
            continue
        for s in range(1 << w):
            if (s >> i) & 1:
                f[s] += f[s ^ (1 << i)]
    
    # 计算完毕后，f[s] 表示 nums 中的是 s 的子集的元素个数
    
    ans = pow2[len(nums)]  # 所有子序列的个数
    
    # 枚举 or_val 的所有子集（包括空集）
    sub = or_val
    while True:
        sign = 1 - (bin(or_val ^ sub).count('1') % 2) * 2
        ans -= sign * pow2[f[sub]]
        if sub == 0:
            break
        sub = (sub - 1) & or_val
    
    return (ans % MOD + MOD) % MOD  # 保证结果非负


def main():
    nums = [1, 2, 3]
    result = count_effective(nums)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

constint MOD = 1000000007;
constint MAX_N = 100001;

// 预处理 2 的幂
vector<int> pow2(MAX_N, 1);

void init() {
    for (int i = 1; i < MAX_N; i++) {
        pow2[i] = (pow2[i-1] * 2LL) % MOD;
    }
}

// 计算整数中 1 的个数
int countBits(int x) {
    return __builtin_popcount(x);
}

int countEffective(vector<int>& nums) {
    int or_val = 0;
    bool same = true;
    for (int x : nums) {
        or_val |= x;
        if (x != nums[0]) {
            same = false;
        }
    }

    // 优化：如果 nums 只有一种数字，那么非空子序列的按位或都是 or_val，只有空子序列的按位或比 or_val 小
    if (same) {
        return1;
    }

    int w = 0;
    int temp = or_val;
    while (temp > 0) {
        w++;
        temp >>= 1;
    }

    vector<int> f(1 << w, 0);
    for (int x : nums) {
        f[x]++;
    }

    for (int i = 0; i < w; i++) {
        if ((or_val >> i) & 1 == 0) {  // 优化：or_val 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到，无需计算
            continue;
        }
        for (int s = 0; s < (1 << w); s++) {
            if ((s >> i) & 1) {
                f[s] += f[s ^ (1 << i)];
            }
        }
    }

    // 计算完毕后，f[s] 表示 nums 中的是 s 的子集的元素个数

    long long ans = pow2[nums.size()];  // 所有子序列的个数

    // 枚举 or_val 的所有子集（包括空集）
    int sub = or_val;
    do {
        int sign = 1 - (countBits(or_val ^ sub) % 2) * 2;
        ans = (ans - sign * pow2[f[sub]] % MOD + MOD) % MOD;
        sub = (sub - 1) & or_val;
    } while (sub != or_val);

    return (ans % MOD + MOD) % MOD;  // 保证结果非负
}

int main() {
    // 初始化幂数组
    init();

    vector<int> nums = {1, 2, 3};
    int result = countEffective(nums);
    cout << result << endl;

    return0;
}