백준 12987
-
백준 12987: Matrix Again코딩 2021. 12. 9. 21:47
https://www.acmicpc.net/problem/12987 12987번: Matrix Again 첫 번째 줄에 N, K, M (1 ≤ N ≤ 50, 1 ≤ K ≤ 109, 1 ≤ M ≤ 104) 이 공백을 구분으로 주어집니다. 다음 N개의 줄에 걸쳐 행렬 A가 주어집니다. (-104 ≤ Aij ≤ 104, 1 ≤ i, j ≤ N) www.acmicpc.net 풀이 분할 정복을 이용하여 쉽게 풀 수 있습니다. $S_T=A+A^2+\dots+A^T$라고 하고, $S_T$를 빠르게 구해 봅시다. $S_{T/2}=A+A^2+\dots+A^{T/2}$이기 때문에, $T$가 짝수일 땐 $S_T=S_{T/2}+A^{T/2}\times S_{T/2}$로 $S_T$를 구할 수 있고, $T$가 홀수일 땐 $S_T..