문제 링크
- http://icpc.me/14559
사용 알고리즘
- 벌레캠프
- 키타마사
시간복잡도
- $O(167^2 log M)$
풀이
문제의 가장 중요한 성질은, $112345^{167} ≡ 1 (mod 10^9+9)$이라는 것입니다.
우리는 총 167개의 지수만 관리해도 충분합니다.
M이 작으면 Naive하게 0이상 167미만인 X에 대해 (용량 mod 167 = X)인 전선의 개수를 관리해주는 방식으로 구할 수 있습니다.
112345의 0제곱부터 166제곱까지 미리 구해놓았다면, 이것은 단순하게 구현할 수 있습니다.
하지만 문제에서는 $M ≤ 10^9$입니다. 이럴때는 믿음을 갖고 벌레캠프를 돌려주면 됩니다.
길이가 167 이하인 점화식이 나오기 때문에 키타마사법이나 행렬 거듭제곱을 이용해 M번째 값을 구해줄 수 있습니다.