2026-10-25：统计有效序列数目。用go语言，给定两个正整数 n 和 k。现在要统计满足下面条件的有序序列数量：序列一共包含 k 个正整数，这

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

1 <= n <= 500000。

1 <= k <= n。

输入： n = 5, k = 3。

输出： 3。

解释：

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

序列

乘积

奇偶性

[1, 1, 3]

1 * 1 * 3 = 3

奇数

[1, 2, 2]

1 * 2 * 2 = 4

偶数

[2, 1, 2]

2 * 1 * 2 = 4

偶数

[2, 2, 1]

2 * 2 * 1 = 4

偶数

[1, 3, 1]

1 * 3 * 1 = 3

奇数

[3, 1, 1]

3 * 1 * 1 = 3

奇数

有 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 个隔板」来数，天然带顺序，不需要额外乘排列数。

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

反过来想：

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

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

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

把 n 写成 n 个 1：

1 1 1 ... 1      （n 个）

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

总 数

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

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

设第 i 项为 ，其中 （这样 自动是正奇数）。

求和：

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

• • 必须是非负整数。

• • 非负性：题目给了 ，所以 恒成立，不用管。

• • 整数性：需要 为偶数。由于 与 奇偶性相同，代码里写成(n+k)%2 == 0。

• •如果不满足，说明根本凑不出「全奇数」序列，减法项为 0，答案就是总数。

满足时，问题变成「k 个非负整数 之和为 」的经典球盒问题，隔板法（允许空盒）给出：

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

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

为 偶 数

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

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

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

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

• • 所有 都与 mod 互质，阶乘取模后非零、可逆；

• • 可以用费马小定理求逆： 。

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

1. 1.正向递推阶乘：fac[i] = fac[i-1] * i % mod，得到 fac[i] = i!。

2. 2.反向递推阶乘逆元：先花一次快速幂算出invF[mx-1] = (499999!)^{-1}，再从后往前用

   递推出所有 invF[i]。

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

步骤 7：comb 就是查表

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

• • ；

• • （因为 ），也在表内；

• • 且 （因为 ），不会出现上标小于下标。

• • 总数： ，对应你表格里那 6 行。

• • n+k = 8 为偶数，需要减全奇数的情况： ，即 ，解数 ，正好对应 [1,1,3]、[1,3,1]、[3,1,1] 这 3 行。

• • 答案：6 − 3 =3，与题目输出一致。

• •k = 1：序列只有 [n]，乘积为偶数当且仅当 n 为偶数。公式给出 ，n 为奇数时减 得 0，n 为偶数时不减得 1。✔

• •k = n：每项只能是 1，乘积恒为 1（奇数）。公式给出 。✔

项目

结论

预处理时间

阶乘正向递推 5×10⁵ 次；阶乘逆元反向递推 5×10⁵ 次；外加一次快速幂，指数为常数 ，约 30 次乘方取模（即 ，可视为常数）

单次查询时间

判断奇偶 + 两次 comb（各 3 次数组访问、2 次乘法取模）

总时间复杂度

，更严谨写为

与 n、k 无关，是常数级预处理 + 常数级查询

总额外空间复杂度

两个长度 5×10⁵ 的全局数组fac与invF。Go 在 64 位平台上int为 8 字节，合计 （约 7.63 MiB），其余只有几个标量变量，为

值得一提的几个点

• •空间换时间：如果每次查询都现算阶乘，是 一次；预处理后变成 一次，代价是约 8 MB 常驻内存。对 n 上限 5×10⁵ 来说这个交换非常划算。

• •mx 的取值刚好卡满：mx = 500000时最大可用下标是 499999，正好等于 n−1 的上限；如果 n 再大一点就会越界，所以数组大小和题目约束是绑定的。

• •费马逆元成立的前提是 mod 为质数且大于所有参与运算的整数，1e9+7 与 5×10⁵ 的组合完全满足；若换成非质数模或与 n 同量级的小模数，这套阶乘逆元就会失效（fac 可能变成 0 而不可逆）。

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:
        return0
    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++完整代码如下：

  

using namespace std;

 constint 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) return0;
    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;

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。