2017/10/31の精進

・ARC058E 和風いろはちゃん

XYZを含まない数列の個数を数えて全体から引くことにする。

XYZを含まない長さi+1の数列は、XYZを含まない長さiの数列にXYZが生じないように数を1つ加えたものである。

ある数を加えたときXYZが生じるか判定するために末尾の数が何個わかっていればいいだろうか?

まず、XYZとなる列の長さは高々17であるから、直前16個がわかっていればいいとかんがえられる。しかしこれでは10^16通りあって十分ではない。

ここで、和が16以下である所までわかっていればいいことに気づく。例えば末尾に1 2 3が並んでいるときビット列110100で表すという方法を用いると、末尾を表すビット列は高々2^16通りしかない。

よってdp[i][j]=長さiで末尾を表すビット列がjであるような数列の個数というDPができる。