• 식을 잘 정리하면 점화식을 찾을수 있긴 한거 같은데, 그 난이도가 그렇게 간단치는 않다 보니 벌리캠프-매시 를 활용해서 선형 점화식을 구하는 연습문제로 유명해졌다.
• 대충 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 문제로 만드는 것이 가능하다고 한다. 이거면 선형 점화식도 필요 없을것 같다!!

(다이아몬드 이상은 코드 생략)

• Dependency
  • teflib.combinatorics.linear_recurrence
  • teflib.combinatorics.find_linear_recurrence