17401. 일하는 세포

세포야 일해라!

17401번: 일하는 세포

---

적혈구는 우리 몸 속의 거점을 돌아다니면서 산소를 운반한다. 적혈구가 혈관을 타고 한 거점에서 다른 거점으로 이동하는 데에는 1초가 걸린다. 그런데 매 초마다 우리 몸 속의 혈관 배치가 달라진다. 다행히 백혈구가 관찰한 결과 $T$초마다 같은 배치가 반복된다는 사실을 알게 되었다.

 

적혈구가 $D$초 동안 이동할 때, 임의의 한 거점에서 다른 거점으로 이동할 수 있는 경로의 수를 구하자. 구하는 답이 매우 커질 수 있으므로 $1e9+7$로 나눈 나머지를 구해야 한다.

풀이

예제 입력을 보자마자 깨달아야 한다. 이 문제는 행렬 곱을 빠르게 구하는 방법을 묻고 있다. 각각의 혈관 지도를 행렬로 생각하고, $D$개의 행렬 곱을 시간 내에 구해야 한다.

 

$i$번째 혈관 지도를 $map[i]$라 정의하자. 구하는 정답은 $\prod_{i=1}^{D}{map[i \mod T]}$이다. 참고로 $\prod$는 각 항의 곱을 의미한다. 그런데 $D$가 최대 $10^{9}$이므로 $O(D)$로는 답을 구할 수 없다.

 

혈관 지도가 $T$초마다 반복된다고 했으므로, $T$개의 혈관 지도가 $D/T$번 반복된 후 $D \mod T$의 혈관 지도가 더 반복된다. 따라서 처음 $T$개의 혈관 지도를 $T/D$번 거듭제곱한 결과에 $\prod_{i=1}^{D \mod T}{map[i]}$를 곱하면 정답을 얻을 수 있다. 행렬의 거듭제곱은 분할 정복 방식으로 구현할 수 있다. 이 글에서는 구현은 다루지 않는다.

주의: 정수 범위

웬만하면 64비트 정수형으로 계산하는 편이 낫다. $1e9+7$의 나머지는 최대 $1e9+6$인데, 이 값을 32비트 정수형 범위에서 제곱할 수 없기 때문이다.

주의: $D = 0$일 때

$D = 0$일 때는 $I$(단위 행렬)를 출력하면 된다.

---

행렬 제곱만 알고 있다면 쉽게 풀 수 있는 문제. 플레 수준은 아닌 듯.