식을 잘 정리하면 점화식을 찾을수 있긴 한거 같은데, 그 난이도가 그렇게 간단치는 않다 보니 벌리캠프-매시 를 활용해서 선형 점화식을 구하는 연습문제로 유명해졌다.
대충 sigma{i^k} 가 k차 다항식이 되어서 선형 점화식으로 표현이 가능하다는 것은 알고 있으니까, 피보나치 텀들이 가중치로 붙은 형태도 선형 점화식이 되지 않을까하고 추측해볼수 있고, 이를 기반으로 믿음의 벌리캠프-매시을 돌려보면 크기가 2k정도인 선형 점화식을 얻을 수 있다.
차수가 O(k)인 선형 점화식에서 n번째 항을 구하는 것은 O(k*2logn)에 계산 가능하다. FFT를 써서 O(klogklogn) 으로 구할수도 있지만, k의 범위가 그리 크지 않아서 O(k*2logn)으로 충분하다.
O(k)개의 초항을 구하는데 O(k), 초항들로부터 벌리캄프-매시 알고리즘을 돌려서 점화식을 찾는 데에 O(k^2), n번째 항을 구하는데에 O(k^2logn)이 걸려서, 전체 시간복잡도는 O(k^2logn).
벌리캄프-매시로 간단히 해결되다보니 정석 풀이는 고민해보지 않았지만, 난이도 평가에 커멘트에는 정석 풀이에 대한 언급이 몇몇 있다. 선형 점화식을 제대로 찾기 위해서는 피보나치 수열의 특성방정식으로부터 이 수열의 특성방정식을 유도 → 수열의 선형 점화식을 유도 → 누적합의 선형 점화식을 유도하는 순서로 진행해서 찾을수 있다고 한다. 하지만 다른 커멘트에서는 단순히 $ F_i i^k = (F_{i+1} - F_{i-1}) i^k $ 를 언급하고 있는데, 이걸 이용하면 간단하게 정리될것 같기도 하다.! 그리도 다른 커멘트에서는 n을 고정하고 k가 하나씩 올라가는 dp 문제로 만드는 것이 가능하다고 한다. 이거면 선형 점화식도 필요 없을것 같다!!