Участник:Hellhoundmipt/build-array-where-you-can-find-the-maximum-exactly-k-comparisons

Материал из DISCOPAL
< Участник:Hellhoundmipt
Версия от 22:36, 6 декабря 2020; Hellhoundmipt (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/submissions/ Scala код <code-cpp> object Solution { val MOD…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/submissions/

Scala код

object Solution {
    val MOD = 1000000007
    def numOfArrays(n: Int, m: Int, k: Int): Int = {
        val dp = Array.fill[Long](n+1, m+1, k+1)(0)
        for (i <- 1 to m) dp(1)(i)(1) = 1
        for {
            i <- 1 to n
            j <- 1 to m
            k <- 1 to k
        } {
            val start = (j * dp(i - 1)(j)(k)) % MOD
            val s = (1L until j).fold(start){ case (acc, x) => (acc + dp(i - 1)(x.toInt)(k - 1)) % MOD }
            dp(i)(j)(k) += s
        }
        (1L to m).fold(0L){ case (acc, i) => (acc + dp(n)(i.toInt)(k)) % MOD }.toInt
    }
}