ARC122 A Many Formulae
解くために必要なパートは次の2つである.
1. 長さ
$ N
の
良い
数列の個数は
$ fib(N)
(
$ 0
項目を
$ 1
,
$ 1
項目を
$ 1
としたフィボナッチ数列)に一致することに気づく, あるいはDPをたてて前計算しておく
2.
寄与分を考える
という典型考察テクニックを適用する.
今回の場合, これらを用いて,
$ A_i
について見ていく(ただし,
$ A_0
は例外処理する)ことによって
$ O(N)
で解くことができる.
実装例:
https://atcoder.jp/contests/arc122/submissions/23388516