调试中...
困难
相关标签
相关企业
提示
给你三个整数 n ，m ，k 。长度为 n 的 好数组 arr 定义如下：
arr中每个元素都在 闭 区间[1, m]中。- 恰好 有
k个下标i（其中1 <= i < n）满足arr[i - 1] == arr[i]。
请你返回可以构造出的 好数组 数目。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：n = 3, m = 2, k = 1
输出：4
解释：
- 总共有 4 个好数组，分别是
[1, 1, 2]，[1, 2, 2]，[2, 1, 1]和[2, 2, 1]。 - 所以答案为 4 。
示例 2：
输入：n = 4, m = 2, k = 2
输出：6
解释：
- 好数组包括
[1, 1, 1, 2]，[1, 1, 2, 2]，[1, 2, 2, 2]，[2, 1, 1, 1]，[2, 2, 1, 1]和[2, 2, 2, 1]。 - 所以答案为 6 。
示例 3：
输入：n = 5, m = 2, k = 0
输出：2
解释：
- 好数组包括
[1, 2, 1, 2, 1]和[2, 1, 2, 1, 2]。 - 所以答案为 2 。
提示：
1 <= n <= 1051 <= m <= 1050 <= k <= n - 1
通过次数
1.3K
提交次数
2.9K
通过率
45.1%
相关企业
提示 1
The first position
arr[0] has m choices.提示 2
For each of the remaining
n - 1 indices, 0 < i < n, select k positions from left to right and set arr[i] = arr[i - 1].提示 3
For all other indices,
set arr[i] != arr[i - 1] with (m - 1) choices for each of the n - 1 - k positions.相似题目
中等
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线
行 1，列 1