[문제 해설]
외친 숫자 X가 최대 100만이기 때문에 모든 확률을 따라가보면서 하면 시간 내에 나오지 않습니다.

이런 문제는 행렬을 이용해서 풀이할 수 있는데, 행렬 A를 다음과 같이 정의합니다.

A[i, j] = i가 j를 가리키고 있을 확률

맨 처음은 항상 나부터 시작하기 때문에 X번째에 어떤 사람이 걸릴 확률은 A^X * (1 0 0 0 ... )  을 계산하면 되는데 이를 다시 정리하면

A^X[0, j] = X번째에 j가 걸릴 확률이 됩니다.

여기에서 A^X 를 빠르게 구하기 위해서는 B에 A^1을 저장한 후에 B를 계속 제곱하면서 곱해나가면 O(lg X)번의 계산으로 A^X를 계산할 수 있습니다. 예를 들어서 A^13 = A^8 * A^4 * A^1 = B^8 * B^4 * B^1 이 됩니다.

아래 소스코드는 Matrix Multiplication을 O(N^3)으로 계산한 코드입니다.


 

이 게시물을..