この間、フィボナッチ数を計算する記事を書いていたら、@fetburner氏にこういう問題を教えて頂いた: T: フィボナッチ – Typical DP Contest | AtCoder フィボナッチ数列の各項は直前の2項(隣接3項間の漸化式)によって定まる\[a_{n+2}=a_n+a_{n+1}\]が、それを「直前の\(K\)項」に一般化したものを高速に計算しなさい、ということだそうだ。\begin{align*}a_1&=a_2=\cdots=a_K=1,\\a_i&=\underbrace{a_{i-1}+\cdots+a_{i-K}}_{K\text{項}}\quad(i>K)\end{align*} 競技プログラミングにはあまり興味はない(制限時間があって他の人と競って〜という形式は好きではない)が、フィボナッチ数列の計算について熱弁した後に「わからん!w」と言って逃げるわけに