跳转至

3339. 查找 K 偶数数组的数量 🔒

题目描述

给定三个整数 n，m 和 k。

一个数组 arr 如果 恰好 有 k 个下标，其中的每个下标 i (0 <= i < n - 1) 满足下述条件，则被称为是 K 偶数的：

  • (arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] 是偶数。

返回长度为 n 的满足 K 偶数 的数组的数量，其中所有元素的范围在 [1, m]。

因为答案可能很大，返回答案对 109 + 7 取模。

 

示例 1：

输入：n = 3, m = 4, k = 2

输出：8

解释：

8 个满足的 2 偶数的数组是：

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

示例 2：

输入：n = 5, m = 1, k = 0

输出：1

解释：

仅有的 0 偶数的数组是 [1, 1, 1, 1, 1]。

示例 3：

输入：n = 7, m = 7, k = 5

输出：5832

 

提示：

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

解法

方法一：记忆化搜索

由于有 $[1, m]$ 个数，那么偶数有 $\textit{cnt0} = \lfloor \frac{m}{2} \rfloor$ 个，奇数有 $\textit{cnt1} = m - \textit{cnt0}$ 个。

我们设计一个函数 $\textit{dfs}(i, j, k)$，表示当前已经填到第 $i$ 个位置，剩余 $j$ 个位置需要满足条件，且上一个位置的奇偶性为 $k$ 的方案数，其中 $k = 0$ 表示上一个位置为偶数，而 $k = 1$ 表示上一个位置为奇数。那么答案就是 $\textit{dfs}(0, k, 1)$。

函数 $\textit{dfs}(i, j, k)$ 的执行逻辑如下：

  • 如果 $j < 0$，表示剩余位置数小于 $0$，直接返回 $0$；
  • 如果 $i \ge n$，表示已经填完了，如果此时 $j = 0$，表示满足条件，返回 $1$，否则返回 $0$；
  • 否则，我们可以选择填奇数或者偶数，分别计算填奇数和填偶数的方案数，最后返回两者之和。

时间复杂度 $O(n \times k)$，空间复杂度 $O(n \times k)$。其中 $n$ 和 $k$ 为题目给定的参数。

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

方法二：动态规划

我们可以将方法一的记忆化搜索转换为动态规划。

定义 $f[i][j][k]$ 表示当前已经填完第 $i$ 个位置，且有 $j$ 个位置满足条件，且上一个位置的奇偶性为 $k$ 的方案数。那么答案就是 $\sum_{k = 0}^{1} f[n][k]$。

初始时，我们将 $f[0][0][1]$ 置为 $1$，表示填完第 $0$ 个位置，且有 $0$ 个位置满足条件，且上一个位置的奇偶性为奇数的方案数为 $1$。其余 $f[i][j][k] = 0$。

状态转移方程如下：

$$ \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} $$

时间复杂度 $O(n \times k)$，空间复杂度 $O(n \times k)$。其中 $n$ 和 $k$ 为题目给定的参数。

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

方法三：动态规划（空间优化）

我们注意到，对于 $f[i]$ 的计算只与 $f[i - 1]$ 有关，因此我们可以使用滚动数组优化空间。

时间复杂度 $O(n \times k)$，空间复杂度 $O(k)$。其中 $n$ 和 $k$ 为题目给定的参数。

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

评论