きたまさ法メモ - よすぽの日記

T: フィボナッチ - Typical DP Contest | AtCoder

僕はこれの解法の理解に非常に時間がかかりました。

なので他の人もきっと時間がかかるよね？ということでメモを残します

まず数列 $a_i$ について

$a_k = d_0 * a_0 + d_1 * a_1 + ... + d_{k-1} * a_{k-1}$
となる $d_0, d_1, ..., d_{k-1}$ が与えられている

ここでf(n) = { $x_0, x_1, ..., x_{k-1}$ }となる関数f(x)を定義する(つまりfは $f: \mathcal{N} -> \mathcal{R}^k$ )
ただし
$a_n = x_0 * a_0 + x_1 * a_1 + ... + x_{k-1} * a_{k-1}$
を満たす

つまり、 $f(k) = \{d_0, d_1, ..., d_{k-1}\}$

ここで, nが渡されるからf(n)をO(k^2 logn)で求める
愚直に行列累乗してしまうともちろんO(k^3 logn)

まず,f(n)がわかっている時に
f(n+1)はO(k)で求められる
これは簡単で
$a_n = x_0 * a_0 + x_1 * a_1 +\ ... +\ x_{k-1} * a_{k-1}$
とすると
$a_{n+1} = x_0 * a_1 + x_1 * a_2 +\ ... +\ x_{k-1} * a_k$
となり
$a_{n+1} = x_0 * a_1 + x_1 * a_2 +\ ... +\ x_{k-1} * \{d_0 * a_0 + d_1 * a_1 ... + d_{k-1} * a_{k-1} \}$
よって結局
$a_{n+1} = (x_0 + x_{k-1} * d_0) * a_0 + (x_1 + x_{k-1} * d_1) * a_1 +\ ... +\ (x_{k-2} * x_{k-1} * d_{k-1}) * a_{k-1}$

またf(n)がわかっていたら, f(2*n)がO(k^2)で求められる
まず、前述の方法により, f(n), f(n+1), f(n+2), ..., f(n+k-1)がO(k^2)で列挙できるのでする
$a_n = x_0 * a_0 + x_1 * a_1 +\ ... +\ x_{k-1} * a_{k-1}$
とすると
$a_{2n} = x_0 * a_{n+0} + x_1 * a_{n+1} + x_2 * a_{n+2} + \ ... +\ x_{k-1} * a_{n+k-1}$
となる(全部の項をn個ずらす)
ここで、f(n), f(n+1), f(n+2), ..., f(n+k-1)が列挙できていたとすると
この式の右側の $a_{n+0}, a_{n+1}, a_{n+k-1}$ は全て $a_0, a_1, ..., a_k$ に分解できる

以上より, f(n) -> f(n+1) と f(n) -> f(2*n) の遷移が出来たまたf(1)もわかっている

全てのnについて,1からスタートして+1と*2の操作をO(logn)回繰り返すことでnが作れれば良い
これはせいぜいDiv1easyぐらい