T: フィボナッチ - Typical DP Contest | AtCoder 僕はこれの解法の理解に非常に時間がかかりました。 なので他の人もきっと時間がかかるよね？ということでメモを残します まず数列 について となるが与えられている ここでf(n) = {}となる関数f(x)を定義する(つまりfは ) ただし を満たす つまり、 ここで, nが渡されるからf(n)をO(k^2 logn)で求める 愚直に行列累乗してしまうともちろんO(k^3 logn) まず,f(n)がわかっている時に f(n+1)はO(k)で求められる これは簡単で とすると となり よって結局 またf(n)がわかっていたら, f(2*n)がO(k^2)で求められる まず、前述の方法により, f(n), f(n+1), f(n+2), ..., f(n+k-1)がO(k^2)で列挙できるのでする とすると となる