yukicoder contest 377 D - Re:010
DPで解くことも出来ます。（この手のDPは「耳DP」と呼ばれることもあるみたいです。）
$ \textrm{dp}[i][j] = 文字列$ S の$ i 文字目まで見て、010の$ j 文字目まで作る方法の総数
と定義します。
$ i+1 文字目を追加するかどうかで場合分けします。
(1) $ i+1 文字目を追加する時
(a)$ i+1 文字目が 0 である時、
$ \textrm{dp}[i+1][1] \space\textrm{+=}\space \textrm{dp}[i][0]
$ \textrm{dp}[i+1][3] \space\textrm{+=}\space \textrm{dp}[i][2] と遷移します。
(b) $ i+1 文字目が 1 である時、
$ \textrm{dp}[i+1][2] \space\textrm{+=}\space \textrm{dp}[i][1] と遷移します。
(c) $ i+1 文字目が ? である時、
(a)(b) の両方の遷移を行います。
(2) $ i+1 文字目を追加しない時
全ての$ j\space(0\leq j\leq 3) について$ \textrm{dp}[i+1][j] \space\textrm{+=}\space \textrm{dp}[i][j] と遷移を行います。
ただし、$ i+1 文字目が?の場合は、0に置き換える場合と1に置き換える場合の$ 2 通りあるので、
$ \textrm{dp}[i+1][j] \space\textrm{+=}\space \textrm{dp}[i][j] \cdot 2 と遷移します。