2026-10-25：统计有效序列数目。用go语言，给定两个正整数 n 和 k。现在要统计满足下面条件的有序序列数量：序列一共包含 k 个正整数，这些数的总和恰好为 n，并且这些数的乘积必须是偶数。序

2026-10-25：统计有效序列数目。用go语言，给定两个正整数 n 和 k。现在要统计满足下面条件的有序序列数量：序列一共包含 k 个正整数，这些数的总和恰好为 n，并且这些数的乘积必须是偶数。序列按位置区分，只要某个位置上的数不同，就算作不同序列。最终结果需要对 1000000007 取余后返回。

1 <= n <= 500000。

1 <= k <= n。

输入： n = 5, k = 3。

输出： 3。

解释：

长度为 k = 3 且和为 5 的序列有：

有 3 个序列的乘积是偶数，因此答案是 3。

题目来自力扣4002。

大体步骤如下：

步骤 1：把题目翻译成组合计数

• 序列有序、有 k 个位置、每个位置是 ≥1 的整数、总和恰好为 n —— 这在组合数学里就是 n 的 k 部分有序分拆（composition）。
• 位置区分意味着 [1,2,2]、[2,1,2]、[2,2,1] 是三个不同序列，可以直接用「把 n 个 1 排成一排、在 n−1 个缝隙里插 k−1 个隔板」来数，天然带顺序，不需要额外乘排列数。

步骤 2：正难则反 —— 用补集

「乘积是偶数」等价于「至少有一个数是偶数」。直接数「至少一个」要分 1 个偶数、2 个偶数……会陷入容斥，很麻烦。

反过来想：

乘积是偶数 = 总数 − 乘积是奇数

而「乘积是奇数」的充要条件是「k 个数全部是奇数」——这个条件非常强、非常好数。于是问题被简化为两个纯组合数相减。

步骤 3：数总数（隔板法 / 星与棒）

把 n 写成 n 个 1：

1 1 1 … 1 （n 个）

中间有 n−1 个空隙，选 k−1 个空隙插板，就把 n 切成 k 段，每段至少 1 个 1，段长就是序列的每一项。

$$\text{总数}=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$

代码里就是 comb(n-1, k-1)。

步骤 4：数「全是奇数」的序列（换元 + 可行性判断）

设第 i 项为 $a_i=2b_i+1$，其中 $b_i\ge 0$（这样 $a_i$ 自动是正奇数）。

求和：

$$\sum a_i=2\sum b_i+k=n⟹\sum _{i=1}^k{b}_i=\frac{n-k}{2}$$

这里出现第一个关键判定：

• $\frac{n-k}{2}$ 必须是非负整数。
• 非负性：题目给了 $k\le n$，所以 $n-k\ge 0$ 恒成立，不用管。
• 整数性：需要 $n-k$ 为偶数。由于 $n-k$ 与 $n+k$ 奇偶性相同，代码里写成 (n+k)%2 == 0。
• 如果不满足，说明根本凑不出「全奇数」序列，减法项为 0，答案就是总数。

满足时，问题变成「k 个非负整数 $b_i$ 之和为 $m=\frac{n-k}{2}$」的经典球盒问题，隔板法（允许空盒）给出：

$$\left(\genfrac{}{}{0ex}{}{m+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{\frac{n-k}{2}+k-1}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{\frac{n+k}{2}-1}{k-1}\right)$$

代码里正是 comb((n+k)/2-1, k-1)。注意 Go 里整数除法天然向下取整，而这个分支只在 n+k 为偶数时才进入，所以不会取错。

步骤 5：合起来得到闭式解

$$\text{ans}=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)-[(n+k)\text{ 为偶数}]\cdot \left(\genfrac{}{}{0ex}{}{\frac{n+k}{2}-1}{k-1}\right)$$

代码里那一句 + mod 是防负数：两个组合数各自都在 $[0,\text{mod})$ 内，相减可能落到负数区间，而 Go 的 % 对负数会返回负余数，所以先加一个 mod 再取模，保证结果落在 $[0,\text{mod})$。

（可以验证减法项永远不超过总数：全奇数序列是总数的一个子集，所以差值必然 ≥ 0，加一次 mod 足够。）

步骤 6：模意义下如何 O(1) 算组合数

模数 $10^9+7$ 是质数，且远大于题目中可能出现的最大下标（n−1 ≤ 499999），因此：

• 所有 $1,2,\dots ,499999$ 都与 mod 互质，阶乘取模后非零、可逆；
• 可以用费马小定理求逆：$x^{-1}\equiv x^{\text{mod}-2}(\mathrm{mod}\text{mod})$。

代码在 init() 里做了两件事：

这个「一次快速幂 + 线性回填」的技巧，把 k 次（甚至 5×10⁵ 次）快速幂压成了 1 次，是这里的核心优化点。

步骤 7：comb 就是查表

$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}=\text{fac}[n]\cdot \text{invF}[m]\cdot \text{invF}[n-m]\mathrm{mod}\text{mod}$$

三次数组访问 + 两次乘法取模，O(1)。题目约束下所有下标都合法：

• $n-1\le 499999=\text{mx}-1$；
• $\frac{n+k}{2}-1\le n-1$（因为 $k\le n$），也在表内；
• 且 $\frac{n+k}{2}-1\ge k-1$（因为 $n\ge k$），不会出现上标小于下标。

步骤 8：代入样例 n=5, k=3 走一遍

• 总数：$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$，对应你表格里那 6 行。
• n+k = 8 为偶数，需要减全奇数的情况：$\frac{n-k}{2}=1$，即 $b_1+b_2+b_3=1$，解数 $\left(\genfrac{}{}{0ex}{}{1+3-1}{3-1}\right)=\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$，正好对应 [1,1,3]、[1,3,1]、[3,1,1] 这 3 行。
• 答案：6 − 3 = 3，与题目输出一致。

步骤 9：两个边界自检（帮助确认公式没错）

• k = 1：序列只有 [n]，乘积为偶数当且仅当 n 为偶数。公式给出 $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$，n 为奇数时减 $\left(\genfrac{}{}{0ex}{}{\cdot }{0}\right)=1$ 得 0，n 为偶数时不减得 1。✔
• k = n：每项只能是 1，乘积恒为 1（奇数）。公式给出 $1-\left(\genfrac{}{}{0ex}{}{n-1}{n-1}\right)=0$。✔

复杂度

值得一提的几个点

• 空间换时间：如果每次查询都现算阶乘，是 $\mathcal{O}(n)$ 一次；预处理后变成 $\mathcal{O}(1)$ 一次，代价是约 8 MB 常驻内存。对 n 上限 5×10⁵ 来说这个交换非常划算。
• mx 的取值刚好卡满：mx = 500000 时最大可用下标是 499999，正好等于 n−1 的上限；如果 n 再大一点就会越界，所以数组大小和题目约束是绑定的。
• 费马逆元成立的前提是 mod 为质数且大于所有参与运算的整数，1e9+7 与 5×10⁵ 的组合完全满足；若换成非质数模或与 n 同量级的小模数，这套阶乘逆元就会失效（fac 可能变成 0 而不可逆）。

Go完整代码如下：

package main

import (
"fmt"
)

const mod = 1_000_000_007
const mx = 500_000

var fac [mx]int // fac[i] = i!
var invF [mx]int // invF[i] = i!^-1 = pow(i!, mod-2)

func init() {
fac[0] = 1
for i := 1; i < mx; i++ {
fac[i] = fac[i–1] * i % mod
}

invF[mx–1] = pow(fac[mx–1], mod–2)
for i := mx – 1; i > 0; i— {
invF[i–1] = invF[i] * i % mod
}
}

func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}

// 从 n 个数中选 m 个数的方案数
func comb(n, m int) int {
return fac[n] * invF[m] % mod * invF[n–m] % mod
}

func countValidSequences(n, k int) int {
ans := comb(n–1, k–1)
if (n+k)%2 == 0 {
ans = (ans – comb((n+k)/2–1, k–1) + mod) % mod // +mod 保证答案非负
}
return ans
}

func main() {
n := 5
k := 3
result := countValidSequences(n, k)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 1_000_000_007
MX = 500_000

fac = [1] * MX # fac[i] = i!
invF = [1] * MX # invF[i] = i!^(-1) = pow(i!, MOD-2)

def init():
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i – 1] * i % MOD

invF[MX – 1] = pow(fac[MX – 1], MOD – 2, MOD)
for i in range(MX – 1, 0, –1):
invF[i – 1] = invF[i] * i % MOD

init()

# 从 n 个数中选 m 个数的方案数
def comb(n, m):
if m < 0 or m > n:
return 0
return fac[n] * invF[m] % MOD * invF[n – m] % MOD

def count_valid_sequences(n, k):
ans = comb(n – 1, k – 1)

if (n + k) % 2 == 0:
ans = (ans – comb((n + k) // 2 – 1, k – 1) + MOD) % MOD

return ans

if __name__ == "__main__":
n = 5
k = 3
result = count_valid_sequences(n, k)
print(result)

C++完整代码如下：

#include <iostream>
using namespace std;

const int MOD = 1'000'000'007;
const int MX = 500'000;

int fac[MX]; // fac[i] = i!
int invF[MX]; // invF[i] = i!^(-1) = pow(i!, MOD-2)

int powmod(int x, int n) {
long long res = 1;
long long base = x;
while (n > 0) {
if (n & 1) res = res * base % MOD;
base = base * base % MOD;
n >>= 1;
}
return (int)res;
}

void init() {
fac[0] = 1;
for (int i = 1; i < MX; ++i) {
fac[i] = (long long)fac[i – 1] * i % MOD;
}

invF[MX – 1] = powmod(fac[MX – 1], MOD – 2);
for (int i = MX – 1; i > 0; —i) {
invF[i – 1] = (long long)invF[i] * i % MOD;
}
}

// 从 n 个数中选 m 个数的方案数
int comb(int n, int m) {
if (m < 0 || m > n) return 0;
return (long long)fac[n] * invF[m] % MOD * invF[n – m] % MOD;
}

int countValidSequences(int n, int k) {
int ans = comb(n – 1, k – 1);
if ((n + k) % 2 == 0) {
ans = (ans – comb((n + k) / 2 – 1, k – 1) + MOD) % MOD; // +MOD 保证答案非负
}
return ans;
}

int main() {
init();

int n = 5;
int k = 3;
int result = countValidSequences(n, k);
cout << result << endl;

return 0;
}