Skip to content

3339. Find the Number of K-Even Arrays πŸ”’

Description

You are given three integers n, m, and k.

An array arr is called k-even if there are exactly k indices such that, for each of these indices i (0 <= i < n - 1):

  • (arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] is even.

Return the number of possible k-even arrays of size n where all elements are in the range [1, m].

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, m = 4, k = 2

Output: 8

Explanation:

The 8 possible 2-even arrays are:

  • [2, 2, 2]
  • [2, 2, 4]
  • [2, 4, 2]
  • [2, 4, 4]
  • [4, 2, 2]
  • [4, 2, 4]
  • [4, 4, 2]
  • [4, 4, 4]

Example 2:

Input: n = 5, m = 1, k = 0

Output: 1

Explanation:

The only 0-even array is [1, 1, 1, 1, 1].

Example 3:

Input: n = 7, m = 7, k = 5

Output: 5832

 

Constraints:

  • 1 <= n <= 750
  • 0 <= k <= n - 1
  • 1 <= m <= 1000

Solutions

Given the numbers $[1, m]$, there are $\textit{cnt0} = \lfloor \frac{m}{2} \rfloor$ even numbers and $\textit{cnt1} = m - \textit{cnt0}$ odd numbers.

We design a function $\textit{dfs}(i, j, k)$, which represents the number of ways to fill up to the $i$-th position, with $j$ remaining positions needing to satisfy the condition, and the parity of the last position being $k$, where $k = 0$ indicates the last position is even, and $k = 1$ indicates the last position is odd. The answer is $\textit{dfs}(0, k, 1)$.

The execution logic of the function $\textit{dfs}(i, j, k)$ is as follows:

  • If $j < 0$, it means the remaining positions are less than $0$, so return $0$;
  • If $i \ge n$, it means all positions are filled. If $j = 0$, it means the condition is satisfied, so return $1$, otherwise return $0$;
  • Otherwise, we can choose to fill with an odd or even number, calculate the number of ways for both, and return their sum.

The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$. Here, $n$ and $k$ are the parameters given in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if j < 0:
                return 0
            if i >= n:
                return int(j == 0)
            return (
                cnt1 * dfs(i + 1, j, 1) + cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0)
            ) % mod

        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        ans = dfs(0, k, 1)
        dfs.cache_clear()
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private Integer[][][] f;
    private long cnt0, cnt1;
    private final int mod = (int) 1e9 + 7;

    public int countOfArrays(int n, int m, int k) {
        f = new Integer[n][k + 1][2];
        cnt0 = m / 2;
        cnt1 = m - cnt0;
        return dfs(0, k, 1);
    }

    private int dfs(int i, int j, int k) {
        if (j < 0) {
            return 0;
        }
        if (i >= f.length) {
            return j == 0 ? 1 : 0;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int a = (int) (cnt1 * dfs(i + 1, j, 1) % mod);
        int b = (int) (cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0) % mod);
        return f[i][j][k] = (a + b) % mod;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        int f[n][k + 1][2];
        memset(f, -1, sizeof(f));
        const int mod = 1e9 + 7;
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        auto dfs = [&](auto&& dfs, int i, int j, int k) -> int {
            if (j < 0) {
                return 0;
            }
            if (i >= n) {
                return j == 0 ? 1 : 0;
            }
            if (f[i][j][k] != -1) {
                return f[i][j][k];
            }
            int a = 1LL * cnt1 * dfs(dfs, i + 1, j, 1) % mod;
            int b = 1LL * cnt0 * dfs(dfs, i + 1, j - (k & 1 ^ 1), 0) % mod;
            return f[i][j][k] = (a + b) % mod;
        };
        return dfs(dfs, 0, k, 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func countOfArrays(n int, m int, k int) int {
    f := make([][][2]int, n)
    for i := range f {
        f[i] = make([][2]int, k+1)
        for j := range f[i] {
            f[i][j] = [2]int{-1, -1}
        }
    }
    const mod int = 1e9 + 7
    cnt0 := m / 2
    cnt1 := m - cnt0
    var dfs func(int, int, int) int
    dfs = func(i, j, k int) int {
        if j < 0 {
            return 0
        }
        if i >= n {
            if j == 0 {
                return 1
            }
            return 0
        }
        if f[i][j][k] != -1 {
            return f[i][j][k]
        }
        a := cnt1 * dfs(i+1, j, 1) % mod
        b := cnt0 * dfs(i+1, j-(k&1^1), 0) % mod
        f[i][j][k] = (a + b) % mod
        return f[i][j][k]
    }
    return dfs(0, k, 1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function countOfArrays(n: number, m: number, k: number): number {
    const f = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(2).fill(-1)),
    );
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    const dfs = (i: number, j: number, k: number): number => {
        if (j < 0) {
            return 0;
        }
        if (i >= n) {
            return j === 0 ? 1 : 0;
        }
        if (f[i][j][k] !== -1) {
            return f[i][j][k];
        }
        const a = (cnt1 * dfs(i + 1, j, 1)) % mod;
        const b = (cnt0 * dfs(i + 1, j - ((k & 1) ^ 1), 0)) % mod;
        return (f[i][j][k] = (a + b) % mod);
    };
    return dfs(0, k, 1);
}

Solution 2: Dynamic Programming

We can convert the memoized search from Solution 1 into dynamic programming.

Define $f[i][j][k]$ to represent the number of ways to fill the $i$-th position, with $j$ positions satisfying the condition, and the parity of the previous position being $k$. The answer will be $\sum_{k = 0}^{1} f[n][k]$.

Initially, we set $f[0][0][1] = 1$, indicating that after filling the $0$-th position, there are $0$ positions satisfying the condition, and the parity of the previous position is odd. All other $f[i][j][k]$ are initialized to $0$.

The state transition equations are as follows:

$$ \begin{aligned} f[i][j][0] &= \left( f[i - 1][j][1] + \left( f[i - 1][j - 1][0] \text{ if } j > 0 \right) \right) \times \textit{cnt0} \bmod \textit{mod}, \ f[i][j][1] &= \left( f[i - 1][j][0] + f[i - 1][j][1] \right) \times \textit{cnt1} \bmod \textit{mod}. \end{aligned} $$

The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$, where $n$ and $k$ are the parameters given in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        f = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        f[0][0][1] = 1
        for i in range(1, n + 1):
            for j in range(k + 1):
                f[i][j][0] = (
                    (f[i - 1][j][1] + (f[i - 1][j - 1][0] if j else 0)) * cnt0 % mod
                )
                f[i][j][1] = (f[i - 1][j][0] + f[i - 1][j][1]) * cnt1 % mod
        return sum(f[n][k]) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int countOfArrays(int n, int m, int k) {
        int[][][] f = new int[n + 1][k + 1][2];
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        final int mod = (int) 1e9 + 7;
        f[0][0][1] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                f[i][j][0]
                    = (int) (1L * cnt0 * (f[i - 1][j][1] + (j > 0 ? f[i - 1][j - 1][0] : 0)) % mod);
                f[i][j][1] = (int) (1L * cnt1 * (f[i - 1][j][0] + f[i - 1][j][1]) % mod);
            }
        }
        return (f[n][k][0] + f[n][k][1]) % mod;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        int f[n + 1][k + 1][2];
        memset(f, 0, sizeof(f));
        f[0][0][1] = 1;
        const int mod = 1e9 + 7;
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                f[i][j][0] = 1LL * (f[i - 1][j][1] + (j ? f[i - 1][j - 1][0] : 0)) * cnt0 % mod;
                f[i][j][1] = 1LL * (f[i - 1][j][0] + f[i - 1][j][1]) * cnt1 % mod;
            }
        }
        return (f[n][k][0] + f[n][k][1]) % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func countOfArrays(n int, m int, k int) int {
    f := make([][][2]int, n+1)
    for i := range f {
        f[i] = make([][2]int, k+1)
    }
    f[0][0][1] = 1
    cnt0 := m / 2
    cnt1 := m - cnt0
    const mod int = 1e9 + 7
    for i := 1; i <= n; i++ {
        for j := 0; j <= k; j++ {
            f[i][j][0] = cnt0 * f[i-1][j][1] % mod
            if j > 0 {
                f[i][j][0] = (f[i][j][0] + cnt0*f[i-1][j-1][0]%mod) % mod
            }
            f[i][j][1] = cnt1 * (f[i-1][j][0] + f[i-1][j][1]) % mod
        }
    }
    return (f[n][k][0] + f[n][k][1]) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function countOfArrays(n: number, m: number, k: number): number {
    const f: number[][][] = Array.from({ length: n + 1 }, () =>
        Array.from({ length: k + 1 }, () => Array(2).fill(0)),
    );
    f[0][0][1] = 1;
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j <= k; ++j) {
            f[i][j][0] = (cnt0 * (f[i - 1][j][1] + (j ? f[i - 1][j - 1][0] : 0))) % mod;
            f[i][j][1] = (cnt1 * (f[i - 1][j][0] + f[i - 1][j][1])) % mod;
        }
    }
    return (f[n][k][0] + f[n][k][1]) % mod;
}

Solution 3: Dynamic Programming (Space Optimization)

We observe that the computation of $f[i]$ only depends on $f[i - 1]$, allowing us to optimize the space usage with a rolling array.

The time complexity is $O(n \times k)$, and the space complexity is $O(k)$, where $n$ and $k$ are the parameters given in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countOfArrays(self, n: int, m: int, k: int) -> int:
        f = [[0] * 2 for _ in range(k + 1)]
        cnt0 = m // 2
        cnt1 = m - cnt0
        mod = 10**9 + 7
        f[0][1] = 1
        for _ in range(n):
            g = [[0] * 2 for _ in range(k + 1)]
            for j in range(k + 1):
                g[j][0] = (f[j][1] + (f[j - 1][0] if j else 0)) * cnt0 % mod
                g[j][1] = (f[j][0] + f[j][1]) * cnt1 % mod
            f = g
        return sum(f[k]) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countOfArrays(int n, int m, int k) {
        int[][] f = new int[k + 1][2];
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        final int mod = (int) 1e9 + 7;
        f[0][1] = 1;
        for (int i = 0; i < n; ++i) {
            int[][] g = new int[k + 1][2];
            for (int j = 0; j <= k; ++j) {
                g[j][0] = (int) (1L * cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0)) % mod);
                g[j][1] = (int) (1L * cnt1 * (f[j][0] + f[j][1]) % mod);
            }
            f = g;
        }
        return (f[k][0] + f[k][1]) % mod;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countOfArrays(int n, int m, int k) {
        vector<vector<int>> f(k + 1, vector<int>(2));
        int cnt0 = m / 2;
        int cnt1 = m - cnt0;
        const int mod = 1e9 + 7;
        f[0][1] = 1;

        for (int i = 0; i < n; ++i) {
            vector<vector<int>> g(k + 1, vector<int>(2));
            for (int j = 0; j <= k; ++j) {
                g[j][0] = (1LL * cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0)) % mod) % mod;
                g[j][1] = (1LL * cnt1 * (f[j][0] + f[j][1]) % mod) % mod;
            }
            f = g;
        }
        return (f[k][0] + f[k][1]) % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func countOfArrays(n int, m int, k int) int {
    const mod = 1e9 + 7
    cnt0 := m / 2
    cnt1 := m - cnt0
    f := make([][2]int, k+1)
    f[0][1] = 1

    for i := 0; i < n; i++ {
        g := make([][2]int, k+1)
        for j := 0; j <= k; j++ {
            g[j][0] = (cnt0 * (f[j][1] + func() int {
                if j > 0 {
                    return f[j-1][0]
                }
                return 0
            }()) % mod) % mod
            g[j][1] = (cnt1 * (f[j][0] + f[j][1]) % mod) % mod
        }
        f = g
    }

    return (f[k][0] + f[k][1]) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function countOfArrays(n: number, m: number, k: number): number {
    const mod = 1e9 + 7;
    const cnt0 = Math.floor(m / 2);
    const cnt1 = m - cnt0;
    const f: number[][] = Array.from({ length: k + 1 }, () => [0, 0]);
    f[0][1] = 1;
    for (let i = 0; i < n; i++) {
        const g: number[][] = Array.from({ length: k + 1 }, () => [0, 0]);
        for (let j = 0; j <= k; j++) {
            g[j][0] = ((cnt0 * (f[j][1] + (j > 0 ? f[j - 1][0] : 0))) % mod) % mod;
            g[j][1] = ((cnt1 * (f[j][0] + f[j][1])) % mod) % mod;
        }
        f.splice(0, f.length, ...g);
    }
    return (f[k][0] + f[k][1]) % mod;
}

Comments