[백준/코틀린] 10830번: 행렬 제곱

링크

10830번: 행렬 제곱

풀이

분할 정복을 이용한 거듭제곱을 행렬에 적용하는 문제입니다.

지수 B가 최대 100,000,000,000이므로,
행렬을 단순히 B번 곱하는 방식은 사용할 수 없습니다.
다음 성질을 활용해 거듭제곱을 분할 정복으로 계산합니다.

• B가 홀수인 경우: $A^B = A \cdot A^{B-1}$
• B가 짝수인 경우: $A^B = (A^{B/2})^2$

위 방식을 통해 O(log B)번의 행렬 곱셈으로 결과를 구할 수 있습니다.\
각 행렬 곱셈의 시간복잡도는 O(N^3)이므로,
전체 시간복잡도는 O(N^3 log B)입니다.

입력 행렬의 원소가 1000일 수 있으므로, 미리 1000으로 나눈 나머지를 저장해야 합니다.

코드

data class Matrix(
    val matrix: List<List<Int>>,
) {
    val n = matrix.size

    operator fun times(other: Matrix): Matrix {
        return Matrix(
            List(n) { i ->
                List(n) { j ->
                    (0 until n).sumOf {
                        this.matrix[i][it] * other.matrix[it][j]
                    } % MOD
                }
            },
        )
    }
}

const val MOD = 1000
val powerCache = HashMap<Long, Matrix>()
fun power(matrix: Matrix, n: Long): Matrix {
    if (powerCache[n] != null) return powerCache.getValue(n)

    return when {
        n == 1L -> matrix
        n % 2 != 0L -> matrix * power(matrix, n - 1)
        else -> power(matrix, n / 2) * power(matrix, n / 2)
    }.also { powerCache[n] = it }
}

fun main() {
    val (n, b) = readln().split(" ").map { it.toLong() }
    val matrix = Matrix(
        List(n.toInt()) {
            readln().split(" ").map { it.toInt() % MOD }
        }
    )

    power(matrix, b).matrix.forEach {
        println(it.joinToString(" "))
    }
}