LeetCode 4002 统计有效序列数目 - Solution

1. 题目数据

题目类型：传统题
题目链接：4002. 统计有效序列数目 - 力扣（LeetCode）

2. 题意简述

给定正整数 $n$ 与 $k$ ，求长度为 $k$ 的正整数序列 $(a_1, a_2, \dots, a_k)$ 的个数，满足 $\sum_{i=1}^k a_i = n$ 且 $\prod_{i=1}^k a_i$ 为偶数，答案对 $10^9+7$ 取模。两个序列在任意位置不同即视为不同。

3. 朴素解法

最直接的想法是枚举所有长度为 $k$ 的正整数序列，验证和与乘积条件。序列空间大小为 $n^k$ ，即使 $n, k$ 仅几十也完全不可接受。

4. 核心解法

特殊性质：乘积为偶数当且仅当至少有一个元素为偶数。因此可以用"总序列数"减去"全奇序列数"。

关键突破：两类计数均可通过隔板法闭式求解，无需枚举。

推导过程：
正整数序列满足 $\sum_{i=1}^k a_i = n$ 的个数是隔板法的标准模型。将 $n$ 个不可区分的球放入 $k$ 个有标号盒子且每个盒子至少一个，等价于在 $n-1$ 个间隙中选 $k-1$ 个放隔板，共 $\binom{n-1}{k-1}$ 种方案。

接下来计算全奇序列数。若每个 $a_i$ 均为奇数，令 $a_i = 2b_i - 1$ （ $b_i \ge 1$ ），则

\sum_{i=1}^k (2b_i - 1) = n \implies \sum_{i=1}^k b_i = \frac{n+k}{2}

此方程有非负整数解当且仅当 $n+k$ 为偶数。此时再用隔板法，方案数为 $\binom{\frac{n+k}{2} - 1}{k - 1}$ 。若 $n+k$ 为奇数，则不存在全奇序列，对应项为 $0$ 。

由容斥原理，最终答案为

\text{ans} = \binom{n-1}{k-1} - \begin{cases} \binom{\frac{n+k}{2} - 1}{k-1} & n \equiv k \pmod{2} \\ 0 & \text{otherwise} \end{cases}

5. 正确性证明

总序列计数：隔板法证明 $\binom{n-1}{k-1}$ 是正整数解总数，无遗漏无重复。

全奇序列计数：变换 $a_i = 2b_i - 1$ 是正整数奇序列与正整数序列之间的双射。方程 $\sum b_i = \frac{n+k}{2}$ 有解当且仅当 $n+k$ 为偶数，此时组合数给出精确计数；若无解则计数为 $0$ 。

容斥（正难则反）：总序列可划分为"至少有一个偶数"和"全奇数"两个互斥类。由于全奇序列是总序列的子集，因此总数不小于全奇数，相减结果非负。

6. 复杂度分析

时间复杂度： $O(k)$ 或 $O(1)$ 。若预计算阶乘与逆元，单次询问可在 $O(1)$ 内完成。
空间复杂度： $O(n)$ 预计算阶乘表，或 $O(1)$ 若使用 math.comb 等内置函数。

7. 实现细节与避坑指南

注意及时取模，同时注意本题答案分两类，两类都要取模。

8. 参考代码

class Solution:
    def countValidSequences(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        total = math.comb(n - 1, k - 1)
        if n % 2 != k % 2:
            return total % MOD
        odd = math.comb((n + k) // 2 - 1, k - 1)
        return (total - odd) % MOD

9. 补充说明

本题是隔板法与容斥原理的经典组合应用，思路简洁但需要细心处理奇偶性条件。
若需处理多组询问，可预处理阶乘与逆元将单次查询降至 $O(1)$ 。
为展现核心逻辑，代码中 math.comb 在 Python 3.8+ 可用，LeetCode 环境已预置该模块。