ARC122 A Many Formulae

解くために必要なパートは次の2つである.

1. 長さ$ Nの良い数列の個数は$ fib(N)($ 0項目を$ 1, $ 1項目を$ 1としたフィボナッチ数列)に一致することに気づく, あるいはDPをたてて前計算しておく

2. 寄与分を考えるという典型考察テクニックを適用する.

今回の場合, これらを用いて, $ A_iについて見ていく(ただし, $ A_0は例外処理する)ことによって$ O(N)で解くことができる.