Welcome to Subscribe On Youtube

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 109​​​​​​​ + 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 * 105
  • 1 <= k <= n

Solutions

Solution 1: Combinatorics

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)$.

  • 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;
    }
};

  • 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


  • 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);
}

All Problems

All Solutions