跳转至

3247. 奇数和子序列的数量 🔒

题目描述

给定一个数组 nums，返回元素和为奇数的 子序列 的数量。

由于答案可能很大，返回答案对 109 + 7 取模。

 

示例 1：

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

输出：4

解释：

奇数和子序列为：[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1].

示例 2：

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

输出：4

解释：

奇数和子序列为：[1, 2, 2], [1, 2, 2], [1, 2, 2], [1, 2, 2].

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

解法

方法一：动态规划

我们定义 \(f[0]\) 表示目前为止的子序列中，和为偶数的子序列个数，而 \(f[1]\) 表示目前为止的子序列中，和为奇数的子序列个数。初始时 \(f[0] = 0\), \(f[1] = 0\)。

遍历数组 \(\textit{nums}\)，对于每个数 \(x\)：

如果 \(x\) 为奇数，那么 \(f[0]\) 和 \(f[1]\) 的更新方式为：

\[ \begin{aligned} f[0] & = (f[0] + f[1]) \bmod 10^9 + 7, \\ f[1] & = (f[0] + f[1] + 1) \bmod 10^9 + 7. \end{aligned} \]

即，当前的和为偶数的子序列个数等于之前的和为偶数的子序列个数，加上之前的和为奇数的子序列拼上当前数 \(x\) 的子序列个数；当前的和为奇数的子序列个数等于之前的和为偶数的子序列拼上当前数 \(x\) 的子序列个数，加上之前的和为奇数的子序列个数，再加上一个只包含当前数 \(x\) 的子序列。

如果 \(x\) 为偶数，那么 \(f[0]\) 和 \(f[1]\) 的更新方式为：

\[ \begin{aligned} f[0] & = (f[0] + f[0] + 1) \bmod 10^9 + 7, \\ f[1] & = (f[1] + f[1]) \bmod 10^9 + 7. \end{aligned} \]

即，当前的和为偶数的子序列个数等于之前的和为偶数的子序列个数，加上之前的和为偶数的子序列拼上当前数 \(x\) 的子序列个数，再加上一个只包含当前数 \(x\) 的子序列；当前的和为奇数的子序列个数等于之前的和为奇数的子序列拼上当前数 \(x\) 的子序列个数，加上之前的和为奇数的子序列个数。

最终，返回 \(f[1]\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{nums}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def subsequenceCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = [0] * 2
        for x in nums:
            if x % 2:
                f[0], f[1] = (f[0] + f[1]) % mod, (f[0] + f[1] + 1) % mod
            else:
                f[0], f[1] = (f[0] + f[0] + 1) % mod, (f[1] + f[1]) % mod
        return f[1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int subsequenceCount(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[2];
        for (int x : nums) {
            int[] g = new int[2];
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int subsequenceCount(vector<int>& nums) {
        const int mod = 1e9 + 7;
        vector<int> f(2);
        for (int x : nums) {
            vector<int> g(2);
            if (x % 2 == 1) {
                g[0] = (f[0] + f[1]) % mod;
                g[1] = (f[0] + f[1] + 1) % mod;
            } else {
                g[0] = (f[0] + f[0] + 1) % mod;
                g[1] = (f[1] + f[1]) % mod;
            }
            f = g;
        }
        return f[1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func subsequenceCount(nums []int) int {
    mod := int(1e9 + 7)
    f := [2]int{}
    for _, x := range nums {
        g := [2]int{}
        if x%2 == 1 {
            g[0] = (f[0] + f[1]) % mod
            g[1] = (f[0] + f[1] + 1) % mod
        } else {
            g[0] = (f[0] + f[0] + 1) % mod
            g[1] = (f[1] + f[1]) % mod
        }
        f = g
    }
    return f[1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function subsequenceCount(nums: number[]): number {
    const mod = 1e9 + 7;
    let f = [0, 0];
    for (const x of nums) {
        const g = [0, 0];
        if (x % 2 === 1) {
            g[0] = (f[0] + f[1]) % mod;
            g[1] = (f[0] + f[1] + 1) % mod;
        } else {
            g[0] = (f[0] + f[0] + 1) % mod;
            g[1] = (f[1] + f[1]) % mod;
        }
        f = g;
    }
    return f[1];
}

评论