4002. Count Valid Sequences

Description

You are given two positive integers n and k.

A valid sequence is a sequence of k positive integers such that:

The sum of all integers in the sequence is equal to n.
The product of all integers in the sequence is even.

Return the number of valid sequences. Since the answer may be very large, return it modulo 10⁹ + 7.

Two sequences are considered different if they differ at any index. For example, [1, 1, 2] and [1, 2, 1] are considered different sequences.

Example 1:

Input: n = 5, k = 3

Output: 3

Explanation:

The sequences of length k = 3 whose sum is 5 are:

Sequence	Product	Parity
`[1, 1, 3]`	`1 * 1 * 3 = 3`	Odd
`[1, 2, 2]`	`1 * 2 * 2 = 4`	Even
`[2, 1, 2]`	`2 * 1 * 2 = 4`	Even
`[2, 2, 1]`	`2 * 2 * 1 = 4`	Even
`[1, 3, 1]`	`1 * 3 * 1 = 3`	Odd
`[3, 1, 1]`	`3 * 1 * 1 = 3`	Odd

There are 3 sequences with an even product, thus the answer is 3.

Example 2:

Input: n = 3, k = 2

Output: 2

Explanation:

The sequences of length k = 2 whose sum is 3 are:

Sequence	Product	Parity
`[1, 2]`	`1 * 2 = 2`	Even
`[2, 1]`	`2 * 1 = 2`	Even

There are 2 sequences with an even product, thus the answer is 2.

Example 3:

Input: n = 5, k = 5

Output: 0

Explanation:

The only possible sequence of length k = 5 whose sum is 5 is [1, 1, 1, 1, 1], which has an odd product. Thus, the answer is 0.

Constraints:

1 <= n <= 5 * 10⁵
1 <= k <= n

Solutions

Solution 1: Combinatorics

Thinking

The number of compositions of \(n\) into \(k\) positive parts is \(\binom{n-1}{k-1}\). The product is even if and only if at least one part is even, so we subtract the all-odd compositions from the total.

All-odd compositions exist only when \(n\) and \(k\) have the same parity. Substituting \(2a_i+1\) yields \(\sum a_i=(n-k)/2\), i.e. \(\binom{(n+k)/2-1}{k-1}\); otherwise that term is \(0\).

With \(n\) and \(k\) up to \(5\times 10^5\), each binomial coefficient needs precomputed factorials and inverse factorials. Queries then subtract modulo \(10^9+7\) in \(O(1)\).

The number of ordered ways to write \(n\) as a sum of \(k\) positive integers is \(\binom{n-1}{k-1}\). An even product means "at least one even number"; the complement is "all odd".

Therefore the answer is:

\[ \binom{n-1}{k-1} - \textit{(number of all-odd sequences)} \]

If every number is odd, write the \(i\)-th number as \(2a_i + 1\) (\(a_i \ge 0\)). Then:

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

All-odd sequences exist only when \(n\) and \(k\) have the same parity (i.e., \(n + k\) is even), and their count is \(\binom{\frac{n+k}{2}-1}{k-1}\); otherwise the count is \(0\).

After precomputing factorials and modular inverses, each combination can be evaluated in \(O(1)\). Return the answer modulo \(10^9+7\).

The time complexity is \(O(N + \log M)\) for preprocessing, and the space complexity is \(O(N)\), where \(N = 5 \times 10^5\) and \(M = 10^9+7\). Each query is \(O(1)\).

Python3JavaC++GoTypeScript

MX = 5 * 10**5 + 1
MOD = 10**9 + 7
f = [1] * MX
g = [1] * MX
for i in range(1, MX):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)


def comb(n: int, k: int) -> int:
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def countValidSequences(self, n: int, k: int) -> int:
        ans = comb(n - 1, k - 1)
        if (n + k) % 2 == 0:
            ans = (ans - comb((n + k) // 2 - 1, k - 1)) % MOD
        return ans

class Solution {
    static final int MX = 500001;
    static final long MOD = 1000000007L;
    static long[] f = new long[MX];
    static long[] g = new long[MX];

    static {
        f[0] = 1;
        g[0] = 1;
        for (int i = 1; i < MX; i++) {
            f[i] = f[i - 1] * i % MOD;
            g[i] = pow(f[i], MOD - 2);
        }
    }

    static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    static long comb(int n, int k) {
        return f[n] * g[k] % MOD * g[n - k] % MOD;
    }

    public int countValidSequences(int n, int k) {
        long ans = comb(n - 1, k - 1);
        if ((n + k) % 2 == 0) {
            ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
        }
        return (int) ans;
    }
}

const int MX = 500001;
const long long MOD = 1000000007LL;

long long f[MX];
long long g[MX];

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int init = []() {
    f[0] = 1;
    g[0] = 1;

    for (int i = 1; i < MX; i++) {
        f[i] = f[i - 1] * i % MOD;
        g[i] = qpow(f[i], MOD - 2);
    }

    return 0;
}();

long long comb(int n, int k) {
    return f[n] * g[k] % MOD * g[n - k] % MOD;
}

class Solution {
public:
    int countValidSequences(int n, int k) {
        long long ans = comb(n - 1, k - 1);

        if ((n + k) % 2 == 0) {
            ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
        }

        return (int) ans;
    }
};

const MX = 500001
const MOD int64 = 1000000007

var f [MX]int64
var g [MX]int64

func init() {
    f[0] = 1
    g[0] = 1

    for i := 1; i < MX; i++ {
        f[i] = f[i-1] * int64(i) % MOD
        g[i] = pow(f[i], MOD-2)
    }
}

func pow(a, b int64) int64 {
    res := int64(1)
    for b > 0 {
        if b&1 == 1 {
            res = res * a % MOD
        }
        a = a * a % MOD
        b >>= 1
    }
    return res
}

func comb(n, k int) int64 {
    return f[n] * g[k] % MOD * g[n-k] % MOD
}

func countValidSequences(n int, 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
    }

    return int(ans)
}

const MX = 500001;
const MOD = 1000000007n;

const f: bigint[] = new Array(MX).fill(1n);
const g: bigint[] = new Array(MX).fill(1n);

function pow(a: bigint, b: bigint): bigint {
    let res = 1n;
    while (b > 0n) {
        if (b & 1n) {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1n;
    }
    return res;
}

for (let i = 1; i < MX; i++) {
    f[i] = (f[i - 1] * BigInt(i)) % MOD;
    g[i] = pow(f[i], MOD - 2n);
}

function comb(n: number, k: number): bigint {
    return (((f[n] * g[k]) % MOD) * g[n - k]) % MOD;
}

function countValidSequences(n: number, k: number): number {
    let ans = comb(n - 1, k - 1);

    if ((n + k) % 2 === 0) {
        ans = (ans - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
    }

    return Number(ans);
}

4002. Count Valid Sequences

Description

Solutions

Solution 1: Combinatorics

Comments