易游国际 2026-04-11: 灵验子序列的数目。用go言语, 给定一个整数数组 nums
2026-04-11：灵验子序列的数目。用go言语，给定一个整数数组 nums，界说“强度”为数组中通盘元素作念按位或运算（OR）的截至。你不错从原数组中删去一些元素但保握剩余元素的相对法例，得到一个非空子序列。若删除这个子序列后，剩尾数组的强度相较原本变小（严格减少），则称这个子序列为“灵验子序列”。条目统计数组中通盘灵验子序列的数目，并对截至取模 1000000007 复返。
备注：若剩尾数组为空，其按位或截至为 0。
1
1
输入： 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] 考据经过
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
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
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
s |= 1
f[s] += f[s^1
}
}
// 策画达成后，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
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
if (s >> i) & 1:
f[s] += f[s ^ (1
# 策画达成后，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
#include
#include
#include
using namespace std;
constint MOD = 1000000007;
constint MAX_N = 100001;
// 预惩处 2 的幂
vector pow2(MAX_N， 1);
void init {
for (int i = 1; i
pow2[i] = (pow2[i-1] * 2LL) % MOD;
}
}
// 策画整数中 1 的个数
int countBits(int x) {
return __builtin_popcount(x);
}
int countEffective(vector& 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 f(1
for (int x : nums) {
f[x]++;
}
for (int i = 0; i
if ((or_val >> i) & 1 == 0) { // 优化：or_val 中是 0 但 s 中是 1 的 f[s] 后头容斥用不到，无需策画
continue;
}
for (int s = 0; s
if ((s >> i) & 1) {
f[s] += f[s ^ (1
}
}
}
// 策画达成后，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 nums = {1， 2， 3};
int result = countEffective(nums);
cout
return0;
}
咱们敬佩东说念主工智能为庸俗东说念主提供了一种“增强器用”，并勤劳于共享全标的的AI学问。在这里，您不错找到最新的AI科普著述、器用评测、普及效果的隐讳以及行业知悉。
迎接温雅“福大大架构师逐日一题”易游国际，发音讯可得回口试贵寓，让AI助力您的异日发展。
澳门在线赌钱娱乐网入口
备案号: