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预处理基础数据预计算2的幂次数组因为长度为n的数组总共有2ⁿ个子序列包含空序列题目要求取模1e97所以提前把2⁰ ~ 2¹⁰⁰⁰⁰⁰全部计算好并取模后续直接调用。计算原数组的总按位或total_or遍历所有元素不断做按位或得到整个数组的强度。快速优化判断如果数组里所有数字都相同直接得出结果这种场景只有删除整个数组这1种有效情况。步骤2位运算宽度计算计算total_or的二进制有效位数w比如total_or3二进制11有效位数w2这个值决定了后续子集枚举的范围总共有2ʷ个二进制子集。步骤3高维前缀和 SOS DP 计算元素子集数量这是核心步骤目的是统计数组中每一个二进制子集s对应的元素个数即数组里有多少个数字它的二进制位是子集s的一部分。初始化计数数组先统计数组中每个数字出现的次数。按位填充计数遍历total_or的每一个二进制位对所有二进制子集进行更新最终得到f[s] 数组中所有二进制位都包含在s里的元素总个数。简单说f[s]是能被s完全“覆盖”的元素数量。优化只处理total_or中为1的二进制位为0的位直接跳过减少计算量。步骤4容斥原理计算无效子序列数量无效子序列删除后剩余元素的强度 total_or。我们用容斥原理枚举total_or的所有子集计算出所有无效子序列的数量。初始值总子序列数量 2ⁿn是数组长度包含空序列。枚举total_or的所有子集对每个子集根据子集的二进制位数计算容斥系数正负交替。用预处理的2的幂次结合f[s]计算该子集对应的子序列数量。用总数量减去/加上对应值剔除所有无效子序列。核心逻辑通过容斥精准筛掉所有「删除后剩余强度不变」的无效子序列。步骤5结果修正与输出对计算结果取模1e97。保证结果为非负数模运算可能出现负数加上模数再取模。最终得到的就是有效子序列的总数。二、以示例 nums[1,2,3] 验证过程原数组强度1|2|33二进制11。总非空子序列数2³-17。无效子序列删除后剩余强度仍为3的子序列共4个。有效子序列 7 - 4 3和题目输出一致。三、时间复杂度 额外空间复杂度1. 时间复杂度设数组长度n最大1e5total_or的二进制有效位数w最大约20因为元素≤1e6。总时间复杂度O(n·w)预处理2的幂次O(1e5) 常数级计算总按位或O(n)SOS DP计算子集计数O(n w·2ʷ)容斥原理枚举子集O(2ʷ)核心瓶颈n·ww是常数≤20因此整体是线性时间能处理1e5的数组。2. 额外空间复杂度O(2ʷ)预处理的幂次数组固定大小1e51常数级子集计数数组f大小为2ʷ≤1e6其余变量都是常数级空间整体空间与数组长度n无关仅由二进制位数决定是极小的常数空间。总结解题核心反向思维总-无效 SOS DP子集统计 容斥原理筛除无效时间复杂度O(n·w)线性复杂度适配1e5数据量额外空间复杂度O(2ʷ)极小的常数空间。Go完整代码如下packagemainimport(fmtmath/bits)constmod1_000_000_007constmaxN100_001varpow2[maxN]int{1}funcinit(){// 预处理 2 的幂fori:1;imaxN;i{pow2[i]pow2[i-1]*2%mod}}funccountEffective(nums[]int)int{or:0same:truefor_,x:rangenums{or|xifx!nums[0]{samefalse}}// 优化如果 nums 只有一种数字那么非空子序列的按位或都是 or只有空子序列的按位或比 or 小ifsame{return1}w:bits.Len(uint(or))f:make([]int,1w)for_,x:rangenums{f[x]}fori:rangew{ifori10{// 优化or 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到无需计算continue}fors:0;s1w;s{s|1i f[s]f[s^1i]}}// 计算完毕后f[s] 表示 nums 中的是 s 的子集的元素个数ans:pow2[len(nums)]// 所有子序列的个数// 枚举 or 的所有子集包括空集forsub,ok:or,true;ok;oksub!or{sign:1-bits.OnesCount(uint(or^sub))%2*2ans-sign*pow2[f[sub]]sub(sub-1)or}return(ans%modmod)%mod// 保证结果非负}funcmain(){nums:[]int{1,2,3}result:countEffective(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportList MOD1_000_000_007MAX_N100_001# 预处理 2 的幂pow2[1]*MAX_Nforiinrange(1,MAX_N):pow2[i]pow2[i-1]*2%MODdefcount_effective(nums:List[int])-int:or_val0sameTrueforxinnums:or_val|xifx!nums[0]:sameFalse# 优化如果 nums 只有一种数字那么非空子序列的按位或都是 or_val只有空子序列的按位或比 or_val 小ifsame:return1wor_val.bit_length()f[0]*(1w)forxinnums:f[x]1foriinrange(w):if(or_vali)10:# 优化or_val 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到无需计算continueforsinrange(1w):if(si)1:f[s]f[s^(1i)]# 计算完毕后f[s] 表示 nums 中的是 s 的子集的元素个数anspow2[len(nums)]# 所有子序列的个数# 枚举 or_val 的所有子集包括空集subor_valwhileTrue:sign1-(bin(or_val^sub).count(1)%2)*2ans-sign*pow2[f[sub]]ifsub0:breaksub(sub-1)or_valreturn(ans%MODMOD)%MOD# 保证结果非负defmain():nums[1,2,3]resultcount_effective(nums)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includebitset#includealgorithmusingnamespacestd;constintMOD1000000007;constintMAX_N100001;// 预处理 2 的幂vectorintpow2(MAX_N,1);voidinit(){for(inti1;iMAX_N;i){pow2[i](pow2[i-1]*2LL)%MOD;}}// 计算整数中 1 的个数intcountBits(intx){return__builtin_popcount(x);}intcountEffective(vectorintnums){intor_val0;boolsametrue;for(intx:nums){or_val|x;if(x!nums[0]){samefalse;}}// 优化如果 nums 只有一种数字那么非空子序列的按位或都是 or_val只有空子序列的按位或比 or_val 小if(same){return1;}intw0;inttempor_val;while(temp0){w;temp1;}vectorintf(1w,0);for(intx:nums){f[x];}for(inti0;iw;i){if((or_vali)10){// 优化or_val 中是 0 但 s 中是 1 的 f[s] 后面容斥用不到无需计算continue;}for(ints0;s(1w);s){if((si)1){f[s]f[s^(1i)];}}}// 计算完毕后f[s] 表示 nums 中的是 s 的子集的元素个数longlonganspow2[nums.size()];// 所有子序列的个数// 枚举 or_val 的所有子集包括空集intsubor_val;do{intsign1-(countBits(or_val^sub)%2)*2;ans(ans-sign*pow2[f[sub]]%MODMOD)%MOD;sub(sub-1)or_val;}while(sub!or_val);return(ans%MODMOD)%MOD;// 保证结果非负}intmain(){// 初始化幂数组init();vectorintnums{1,2,3};intresultcountEffective(nums);coutresultendl;return0;}