零乘积子序列计数问题：我的C++解法为何出错？

问题描述 #

给定一个包含n个整数的数组arr，统计其中满足「最小值与最大值的乘积为0」的非空子序列数量，结果需对10^9+7取模。子序列定义为删除数组若干元素（可删0个）且不改变剩余元素顺序得到的序列。

示例 #

输入n=3，arr=[1,0,-2]，共有7个非空子序列，其中满足条件的是[1,0]、[0]、[0,-2]，正确答案为3。

我的解法与问题 #

我通过统计数组中零、正数、负数的数量，利用2^n计算可能的子序列数求和，但运行示例得到结果10，与预期3不符，恳请指出错误。

附我的C++代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long

int zeroSubs(vector<int> arr){
    int x = 0, y = 0, z = 0, ans = 0;
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] == 0) z++;
        else if(arr[i] < 0) x++;
        else y++;
    }
    ans += ((int)pow(2, z))*((int)pow(2, x));
    ans += ((int)pow(2, y))*((int)pow(2, z));
    ans += ((int)pow(2, z));

    return ans;
}

int32_t main()
{
//directly passed the sample test case as an array
    cout<<zeroSubs({1, 0, -2});
    return 0;
}

错误分析 #

你的代码存在三个核心问题：

1. 逻辑完全偏离题目要求
   题目要求的是「子序列最小值与最大值乘积为0」，即：

   • 子序列必须包含0，且不同时包含正数和负数（如果同时有正、负、0，最小值是负数，最大值是正数，乘积为负，不符合条件）。
     而你的公式统计的是「所有0与负数的组合 + 所有0与正数的组合 + 所有0的组合」，不仅包含了空序列，还错误计入了只含负数/正数的无效子序列，同时重复计算了仅含0的子序列。

2. 使用pow计算幂次的精度问题
   pow是浮点数函数，当指数较大时会出现精度丢失，导致计算的2^n结果不准确，应该用整数快速幂实现幂次计算。

3. 未处理空序列与取模
   你的公式包含了空序列（比如2^z包含选0个0的情况），且未对结果取模，进一步放大了误差。

正确思路与代码 #

正确的计算逻辑是：

1. 先计算所有包含至少一个0的非空子序列数：总非空子序列数减去不含任何0的非空子序列数，即2^total - 2^(total-z)（total是数组总元素数，z是0的数量）。
2. 再减去同时包含0、至少一个正数、至少一个负数的无效子序列数：这类子序列的min为负、max为正，乘积不为0，数量是(2^z-1)*(2^y-1)*(2^x-1)（x是负数数量，y是正数数量）。
3. 最终结果对10^9+7取模，注意减法后需加模保证结果非负。

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

// 快速幂计算base^exp mod MOD，避免浮点数精度问题
long long quick_pow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

int countValidSubsequences(vector<int>& arr) {
    int total = arr.size();
    int neg_cnt = 0, pos_cnt = 0, zero_cnt = 0;
    for (int num : arr) {
        if (num == 0) zero_cnt++;
        else if (num < 0) neg_cnt++;
        else pos_cnt++;
    }
    
    // 计算包含至少一个0的非空子序列数
    long long has_zero = (quick_pow(2, total) - quick_pow(2, total - zero_cnt) + MOD) % MOD;
    // 计算同时包含0、正、负数的无效子序列数
    long long invalid = 0;
    if (neg_cnt > 0 && pos_cnt > 0 && zero_cnt > 0) {
        invalid = ((quick_pow(2, zero_cnt) - 1) * (quick_pow(2, pos_cnt) - 1)) % MOD;
        invalid = (invalid * (quick_pow(2, neg_cnt) - 1)) % MOD;
    }
    // 最终有效子序列数
    long long ans = (has_zero - invalid + MOD) % MOD;
    return ans;
}

int main() {
    vector<int> arr = {1, 0, -2};
    cout << countValidSubsequences(arr) << endl;
    return 0;
}

运行上述代码，示例输入会输出正确结果3。

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