第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion

解法

各マスの操作のされ方は、

のどちらかです。そして各マスがそのどちらになるかは、実は端から順番に決めていくことができます。

まず左端の1マス目を見てみます。これは必ず区間の始点になるので、左端のマスは必ず1回だけ反転します。なのでもし左端のマスの初期色が白だったら、どうやっても黒になってしまうので即アウト（0通り）です。

次に2マス目の扱い方は、「1番目のマスとペアにして終点となる」「右にあるマスとペアにして始点となる」の2択です。そして前者なら1回、後者なら2回、2番目のマスが反転します。なので2番目のマスの初期色が黒だったら前者、白だったら後者を選ぶ必要があり、終点/始点のどちらにするかが一意に決まります。

f:id:betrue12:20190825013226p:plain

この考え方は一般化できます。つまり自分より左のマスの扱いが全て決まっていれば「左から何本、閉じていない操作区間が伸びてきているか」が分かり、その偶奇と自分の初期色から、自分が終点/始点のどちらになるべきなのかが一意に決まります。

より具体的に考えましょう。 $i-1$ マス目までの終点/始点を決めた時点で、 $i$ マス目に伸びてきている閉じていない操作区間が $k_{i}$ 個あるとします。このとき、もし $i$ マス目の初期色が白だったら、 $i$ マス目の反転回数が偶数にならないといけないので

$k_{i}$ が偶数である場合、 $i$ マス目はこれまでの始点の「どれか」とペアにして終点となる。ここで場合の数が $k_{i}$ 倍され、次に伸びる区間は $k_{i+1} = k_{i} - 1$ 個。
$k_{i}$ が奇数である場合、 $i$ マス目は新しい区間の始点となる。次に伸びる区間は $k_{i+1} = k_{i} + 1$ 個。