BOJ 13328, Message Passing

2016년 ACM-ICPC 한국 인터넷 예선 D번 문제였던 Message Passing 입니다. 규칙을 찾고, 길이가 몇차든, 항이 M개인 선형 점화식의 N번째 항을 O(M^3 logN)에 구하는 방법을 알고 있다면 풀 수 있는 문제였습니다.

문제에 쓰여 있는규칙을 n=2, n=3일때 몇 번 나열해본다면, 위의 규칙은 모두 피보나치 수열과 유사한 형태의 규칙을 띈다고 생각하시면 됩니다.

위의 규칙을 깨달았다면?

문제의 70%는 해결 되었습니다.

이 문제를 설명하기 위해선 여러가지 문제를 거쳐야 합니다.

먼저

BOJ 2749번 

피보나치 수 3

문제입니다. 

이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 

이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다.

수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면

과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 

입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면!

이 될 것이고

이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다.

n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.

그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이 필요하죠. 하지만, 문제에서 요구하는 t의 범위가 20억 (2*10^9)이니 위의 시간복잡도로 풀기엔 아직도 턱없이 부족합니다.

그러므로, 위에 서술한대로 시간 복잡도를 O(N^3logM)으로 줄이기 위해선, 어떤 수의 거듭제곱을 빠르게 구하는 알고리즘인 Fast Power Algorithm을 사용해야합니다.

위 문제는 이 식을 행렬에 응용한 것 뿐이죠!

n=2일때 답을 구하는 방법을 알았으니, 이제 n=50일때의 답도 쉽게 구할 수 있습니다.

규칙을 찾아 알려드리자면, n=50일때의 행렬은

와 같은 꼴을 가지고 있습니다.

물론, n=50일때의 선형 점화식은

입니다.

단, 행렬을 곱할 때 수가 커질 수 있으므로, 문제의 지시대로 각 행렬의 모든 원소를 계산할 때 마다 31991로 나눠줘야 합니다.