[BOJ] 16725 다항 계수 - P5

문제풀이

1. 문제의 노트에 주어진 다항식을 푸는 방식의 누적합을 이용한 풀이

---

주의사항

1. 나머지 계산할 때 음수값이 나오는 것을 조심하자.

---

소요시간

40분

---

package 백준.Platinum.P5.p16725_다항계수

const val MOD = 1_000_000_009
fun main() {
    val (N, M, K) = readln().split(" ").map(String::toInt)
    fun result(): Long {
        val arr = LongArray(K + 1)
        arr.fill(1, 0, minOf(K + 1, N + 1))
        val sumArr = LongArray(K + 1)
        for (k in 1 until M) {
            for (i in 0..minOf(K, N * M)) {
                sumArr[i] = (sumArr[i] + arr[i]) % MOD
                if (i + N + 1 <= K) sumArr[i + N + 1] = (sumArr[i + N + 1] - arr[i] + MOD) % MOD
            }
            var value = 0L
            for (i in 0..minOf(K, N * (M + 1))) {
                value = (value + sumArr[i]) % MOD
                arr[i] = value
            }
            sumArr.fill(0, 0, minOf(K, N * (M + 1)) + 1)
        }
        return arr[K]
    }
    println(result())
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p16725_%EB%8B%A4%ED%95%AD%EA%B3%84%EC%88%98/p16725_%EB%8B%A4%ED%95%AD%EA%B3%84%EC%88%98.kt

---

문제링크

https://www.acmicpc.net/problem/16725