글 읽기 - 17272 리그오브 레전설(Large) 푸는 알고리즘이 있나요?

17271 리그오브 레전설(Small)은 탑다운 Dp로 풀었습니다

Large는 n이 long long범위길래 Cycle 찾아서 MOD로 푸는 건가 했는데 그래도 MOD 가 10억7이라 메모리나 시간상 안 될 것 같고..

혹시 따로 알고리즘이나 풀이법이 있다면 알려주실수 있나요?

수를 조합하는 것에 대한 알고리즘으로 검색해봐도 안나오더라구요ㅠㅠ

다른 분들 코드를 봐도 어떤식으로 푸신건지 잘 모르겠습니다. M의 범위는 100이기에 M을 이용해 푸시던데..

행렬 곱셈이나 소위 키타마사법으로 풀 수 있습니다. 둘 다 검색하면 나옵니다.

죄송합니다 잘 안 나오네요 있긴 있을텐데 요는 문제의 점화식을 행렬 곱셈을 통해서 표현할 수 있다는 겁니다. 그러면 O(m^3 log n)에 풀 수 있습니다.

행렬 곱셈, 소위 키타마사법 모두 처음들어봤네요 ㅠㅠ

공부 해보겠습니다 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge