Hard
You are given three integers n
, m
and k
. Consider the following algorithm to find the maximum element of an array of positive integers:
You should build the array arr which has the following properties:
arr
has exactly n
integers.1 <= arr[i] <= m
where (0 <= i < n)
.arr
, the value search_cost
is equal to k
.Return the number of ways to build the array arr
under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 109 + 7
.
Example 1:
Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
Example 2:
Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.
Example 3:
Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
Constraints:
1 <= n <= 50
1 <= m <= 100
0 <= k <= n
class Solution {
fun numOfArrays(n: Int, m: Int, k: Int): Int {
var ways = Array(m + 1) { LongArray(k + 1) }
var sums = Array(m + 1) { LongArray(k + 1) }
for (max in 1..m) {
ways[max][1] = 1
sums[max][1] = ways[max][1] + sums[max - 1][1]
}
for (count in 2..n) {
val ways2 = Array(m + 1) { LongArray(k + 1) }
val sums2 = Array(m + 1) { LongArray(k + 1) }
for (max in 1..m) {
for (cost in 1..k) {
val noCost = max * ways[max][cost] % MOD
val newCost = sums[max - 1][cost - 1]
ways2[max][cost] = (noCost + newCost) % MOD
sums2[max][cost] = (sums2[max - 1][cost] + ways2[max][cost]) % MOD
}
}
ways = ways2
sums = sums2
}
return sums[m][k].toInt()
}
companion object {
private const val MOD = 1000000007
}
}