SRM555 Div1Hard の元の問題の解法

各開始位置について「ここはgoalと違っても良い」と「ここだけしかgoalと違ってなかったらだめ」の２つのマスク(X,Yとします)を作ります。
すると、各開始位置での正しい初期位置の集合はドーナツ型の集合になります。
ここで、ドーナツ型の集合の包除原理をする必要が出てきます。
これは、包除原理の中で包除原理をすれば良いです。
計算量はO(3^開始位置の個数)くらいです。開始位置の個数は12個くらいまでならいけそうです。
開始位置の個数が13個以上のケースをなんとかしなければなりません。
「開始位置の個数=テープの長さ-実行範囲+1」が成り立ち、テープの長さが30くらいなので、実行範囲が18以下の場合についていい感じに解きたいです。
ここからは今の問題の解法と同じなのですが、直前数bitを持つbitDPとかでできるんだっけか。
という感じです。

ちなみに、出し損ねたドーナツ型集合の包除原理は、TCO13 Semifinal2 easyとして出題しました。