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

Thinking

We count length-\(n\) arrays over \([1,m]\) with exactly \(k\) adjacent even pairs. Only parity matters: there are \(\lfloor m/2 \rfloor\) evens and \(m-\lfloor m/2 \rfloor\) odds.

State \((i,j,\textit{last})\) is the number of ways after \(i\) positions, with \(j\) even-pairs left and a given previous parity. An even costs one pair only when the previous value was even.

Negative \(j\) is zero; a finished array scores one iff \(j=0\). The dummy previous parity is odd so the first cell cannot form a pair.

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

Thinking

The memoized recursion is slower in some languages. The same transition is a layer DP: \(f[i][j][0/1]\) after \(i\) positions, \(j\) even-pairs, and a last parity.

An even comes from an odd last cell or from an even last cell with \(j-1\) pairs; an odd never increases the pair count. \(f[0][0][1]=1\) matches the search base.

The answer is \(f[n][k][0]+f[n][k][1]\).

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)

Thinking

\(f[i]\) depends only on \(f[i-1]\), so the first index of the table can be dropped.

A buffer \(g\) receives the new layer and then replaces \(f\), cutting space to \(O(k)\) without changing the time exponent.

The answer is still the sum of the two parities at \(j=k\) after \(n\) layers.

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