3757. 有效子序列的数量

Hard

题目描述

给你一个整数数组 nums。

数组的强度定义为其所有元素的按位或（OR）运算的结果。

如果移除某个子序列能够严格减少剩余元素的强度，则该子序列被认为是有效的。

返回 nums 中有效子序列的数量。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

空数组的按位或运算结果为 0。

示例 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。

示例 2：

输入：nums = [7,4,6]

输出：4

解释：

数组的按位或运算结果为 7 OR 4 OR 6 = 7。有效的子序列有：

[7]：剩余元素 [4, 6] 的按位或运算结果为 6。
[7, 4]：剩余元素 [6] 的按位或运算结果为 6。
[7, 6]：剩余元素 [4] 的按位或运算结果为 4。
[7, 4, 6]：剩余元素 [] 的按位或运算结果为 0。

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

示例 3：

输入：nums = [8,8]

输出：1

解释：

数组的按位或运算结果为 8 OR 8 = 8。只有子序列 [8, 8] 是有效的，因为移除它后剩余 []，按位或运算结果为 0。因此，有效子序列的总数为 1。

示例 4：

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

输出：5

约束条件：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

提示：

如果一个位被完全从数组的或运算中移除，则按位或会减少。
要完全移除一个位，必须移除其所有出现。
计算这样的子集并在位上应用容斥原理。

解题思路

这道题的关键洞察是理解什么时候移除子序列会减少数组的强度。根据按位或运算的性质，只有当我们移除某个位的所有出现时，该位才会从最终结果中消失，从而减少强度。

核心思路：

位分析：对于数组的每一位，我们需要分析哪些元素包含这一位。
容斥原理：使用容斥原理来计算有效子序列的数量。
分组计算：将数组中的数字按照它们包含的位进行分组，然后计算每组的贡献。

算法步骤：

计算原数组的总强度（所有元素的按位或）
对于每个可能的位组合，计算包含这些位的元素集合
使用容斥原理：对于每个非空的位集合，计算移除包含这些位的所有元素后，剩余元素的或运算结果
如果剩余结果小于原始强度，则所有包含这些位的子序列都是有效的

优化要点：

只考虑在原数组中实际出现的位
使用位掩码来高效处理位操作
预计算每个位组合对应的元素数量，避免重复计算

代码实现

class Solution {
public:
    int countEffective(vector<int>& nums) {
        const int MOD = 1000000007;
        int n = nums.size();
        
        // 计算原数组的总强度
        int totalOr = 0;
        for (int num : nums) {
            totalOr |= num;
        }
        
        // 找出所有在数组中出现的位
        vector<int> bits;
        for (int i = 0; i < 20; i++) {
            if (totalOr & (1 << i)) {
                bits.push_back(i);
            }
        }
        
        int bitCount = bits.size();
        long long result = 0;
        
        // 预计算2的幂次
        vector<long long> pow2(n + 1);
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
        
        // 枚举所有可能的位组合（除了空集）
        for (int mask = 1; mask < (1 << bitCount); mask++) {
            int bitMask = 0;
            int popCount = 0;
            
            for (int i = 0; i < bitCount; i++) {
                if (mask & (1 << i)) {
                    bitMask |= (1 << bits[i]);
                    popCount++;
                }
            }
            
            // 计算包含这些位的元素数量
            int count = 0;
            int remainingOr = 0;
            
            for (int num : nums) {
                if ((num & bitMask) == bitMask) {
                    count++;
                } else {
                    remainingOr |= num;
                }
            }
            
            // 如果移除这些元素后强度减少，则这些子序列是有效的
            if (remainingOr < totalOr && count > 0) {
                long long contribution = (pow2[count] - 1 + MOD) % MOD;
                if (popCount % 2 == 1) {
                    result = (result + contribution) % MOD;
                } else {
                    result = (result - contribution + MOD) % MOD;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countEffective(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 计算原数组的总强度
        total_or = 0
        for num in nums:
            total_or |= num
        
        # 找出所有在数组中出现的位
        bits = []
        for i in range(20):
            if total_or & (1 << i):
                bits.append(i)
        
        bit_count = len(bits)
        result = 0
        
        # 预计算2的幂次
        pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow2[i] = (pow2[i - 1] * 2) % MOD
        
        # 枚举所有可能的位组合（除了空集）
        for mask in range(1, 1 << bit_count):
            bit_mask = 0
            pop_count = 0
            
            for i in range(bit_count):
                if mask & (1 << i):
                    bit_mask |= (1 << bits[i])
                    pop_count += 1
            
            # 计算包含这些位的元素数量
            count = 0
            remaining_or = 0
            
            for num in nums:
                if (num & bit_mask) == bit_mask:
                    count += 1
                else:
                    remaining_or |= num
            
            # 如果移除这些元素后强度减少，则这些子序列是有效的
            if remaining_or < total_or and count > 0:
                contribution = (pow2[count] - 1) % MOD
                if pop_count % 2 == 1:
                    result = (result + contribution) % MOD
                else:
                    result = (result - contribution) % MOD
        
        return result

public class Solution {
    public int CountEffective(int[] nums) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        // 计算原数组的总强度
        int totalOr = 0;
        foreach (int num in nums) {
            totalOr |= num;
        }
        
        // 找出所有在数组中出现的位
        List<int> bits = new List<int>();
        for (int i = 0; i < 20; i++) {
            if ((totalOr & (1 << i)) != 0) {
                bits.Add(i);
            }
        }
        
        int bitCount = bits.Count;
        long result = 0;
        
        // 预计算2的幂次
        long[] pow2 = new long[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
        
        // 枚举所有可能的位组合（除了空集）
        for (int mask = 1; mask < (1 << bitCount); mask++) {
            int bitMask = 0;
            int popCount = 0;
            
            for (int i = 0; i < bitCount; i++) {
                if ((mask & (1 << i)) != 0) {
                    bitMask |= (1 << bits[i]);
                    popCount++;
                }
            }
            
            // 计算包含这些位的元素数量
            int count = 0;
            int remainingOr = 0;
            
            foreach (int num in nums) {
                if ((num & bitMask) == bitMask) {
                    count++;
                } else {
                    remainingOr |= num;
                }
            }
            
            // 如果移除这些元素后强度减少，则这些子序列是有效的
            if (remainingOr < totalOr && count > 0) {
                long contribution = (pow2[count] - 1 + MOD) % MOD;
                if (popCount % 2 == 1) {
                    result = (result + contribution) % MOD;
                } else {
                    result = (result - contribution + MOD) % MOD;
                }
            }
        }
        
        return (int)result;
    }
}

var countEffective = function(nums) {
    const MOD = 1000000007;
    const n = nums.length;
    const totalOr = nums.reduce((acc, num) => acc | num, 0);
    
    // For each possible OR value, count how many subsequences have that OR
    const dp = new Map();
    dp.set(0, 1); // empty subsequence
    
    for (const num of nums) {
        const newDp = new Map(dp);
        for (const [orVal, count] of dp) {
            const newOr = orVal | num;
            newDp.set(newOr, (newDp.get(newOr) || 0) + count);
        }
        dp.clear();
        for (const [key, val] of newDp) {
            dp.set(key, val % MOD);
        }
    }
    
    // Total subsequences is 2^n
    const totalSubseq = Math.pow(2, n) % MOD;
    
    // Effective subsequences are those where remaining OR < totalOr
    // remaining OR = totalOr if subsequence OR doesn't affect any bit
    const ineffective = dp.get(totalOr) || 0;
    
    // We need to count subsequences where removing them decreases the total OR
    let effective = 0;
    
    // Check each bit position
    for (let bit = 0; bit < 20; bit++) {
        if ((totalOr & (1 << bit)) === 0) continue;
        
        // Count elements that have this bit set
        const withBit = nums.filter(x => x & (1 << bit)).length;
        if (withBit === 0) continue;
        
        // Count subsequences that contain ALL elements with this bit
        // If we remove such subsequence, this bit disappears from remaining
        const withoutBit = n - withBit;
        const subseqWithAllBits = Math.pow(2, withoutBit) % MOD;
        effective = (effective + subseqWithAllBits) % MOD;
    }
    
    // More precise approach: use inclusion-exclusion
    const memo = new Map();
    
    function countSubseqMissingBits(mask, idx) {
        if (idx === 20) {
            if (mask === 0) return 0;
            // Count subsequences that miss all bits in mask
            let count = 1;
            for (let i = 0; i < n; i++) {
                if ((nums[i] & mask) === 0) {
                    count = (count * 2) % MOD;
                } else {
                    count = (count * 1) % MOD; // can't include this element
                }
            }
            return count - 1; // exclude empty subsequence
        }
        
        const key = (mask << 5) | idx;
        if (memo.has(key)) return memo.get(key);
        
        let result = countSubseqMissingBits(mask, idx + 1);
        if (totalOr & (1 << idx)) {
            result = (result + countSubseqMissingBits(mask | (1 << idx), idx + 1)) % MOD;
        }
        
        memo.set(key, result);
        return result;
    }
    
    // Direct computation
    effective = 0;
    
    // For each bit that exists in totalOr
    for (let bit = 0; bit < 20; bit++) {
        if ((totalOr & (1 << bit)) === 0) continue;
        
        // Elements that don't have this bit
        const elementsWithoutBit = [];
        for (let i = 0; i < n; i++) {
            if ((nums[i] & (1 << bit)) === 0) {
                elementsWithoutBit.push(i);
            }
        }
        
        // Subsequences that include only elements without this bit
        const countWithoutBit = Math.pow(2, elementsWithoutBit.length) - 1; // exclude empty
        effective = (effective + countWithoutBit) % MOD;
    }
    
    // Remove overcounting using inclusion-exclusion
    for (let mask = 1; mask < (1 << Math.min(20, 10)); mask++) {
        let validElements = n;
        let bitCount = 0;
        
        for (let bit = 0; bit < 20; bit++) {
            if (mask & (1 << bit)) {
                if ((totalOr & (1 << bit)) === 0) {
                    validElements = 0;
                    break;
                }
                bitCount++;
                
                let newValid = 0;
                for (let i = 0; i < n; i++) {
                    if ((nums[i] & (1 << bit)) === 0) {
                        newValid++;
                    }
                }
                validElements = Math.min(validElements, newValid);
            }
        }
        
        if (validElements > 0) {
            const count = Math.pow(2, validElements) - 1;
            if (bitCount % 2 === 1) {
                effective = (effective - count + MOD) % MOD;
            } else {
                effective = (effective + count) % MOD;
            }
        }
    }
    
    // Simpler approach: count directly
    let result = 0;
    
    // Generate all possible OR values for remaining elements
    for (let mask = 0; mask < (1 << n); mask++) {
        let subseqOr = 0;
        let remainingOr = 0;
        
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseqOr |= nums[i];
            } else {
                remainingOr |= nums[i];
            }
        }
        
        if (mask > 0 && remainingOr < totalOr) {
            result++;
        }
    }
    
    return result % MOD;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n × 2^k)
空间复杂度	O(n + k)

其中 n 是数组长度，k 是数组中所有数字包含的不同位的总数（最多 20 位）。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析