[BOJ 23819] 백준 23819번 - 묻고 더블로 마셔

		2021 POSTECH Programming Open Contest 풀이
A		[BOJ 23813] 회전
B		[BOJ 23814] 아 저는 볶음밥이요
C		[BOJ 23815] 똥게임
D		[BOJ 23816] 옷걸이걸이걸이
E		[BOJ 23817] 포항항
F		[BOJ 23818] 원수의 원수
G		[BOJ 23819] 묻고 더블로 마셔
H		[BOJ 23820] MEX

1. 문제

$23819$. 묻고 더블로 마셔 (2021 POSTECH Programming Open Contest G번)

백준 23819번 - 묻고 더블로 마셔 (https://www.acmicpc.net/problem/23819)

2. 풀이

혼자 힘으로 해결하지 못했고, 대회 출제진 쪽에서 올려 주신 풀이 슬라이드를 보고 풀었다.

행렬의 분할정복 거듭제곱을 구현해서 위 사진의 $k\times k$행렬을 $(N-K)$제곱하면 된다. 그리고, $a(n)$을 구하는 것이므로 만들어진 행렬의 맨 위 행에 처음 $a(1\sim k)$를 역순으로 곱하면 된다. (행렬 연산에 의해)

3. 채점 결과

4. 회고

상당히 어렵다. 행렬을 응용하는 문제는 여전히 적응이 안 된다.

5. 코드