読者です 読者をやめる 読者になる 読者になる

きたまさ法メモ

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ぐらい