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 = [&](this 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(i + 1, j, 1) % mod;
            int b = 1LL * cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0) % mod;
            return f[i][j][k] = (a + b) % mod;
        };
        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
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