SRM504 Div1 500

とぷこだ 過去問

問題

ある2次元グリッドにW(白)かB(黒)が描かれてたものが与えられたとき、そのグリッドについて、(i,j)と(i,j+1)の色が、

  • (白,白) : なにもしない
  • (黒,白) : その下の2つ(i+1,j)と(i+1,j+1)の色を黒にする
  • (白,黒) : その下の2つ(i+1,j)と(i+1,j+1)の色を白にする
  • (黒,黒) : その下の2つ(i+1,j)と(i+1,j+1)の色をswapする

というプログラムを左(0,0)から右(W-1,0)、上から下へ連続的に行う機械がある。
この機械で生成されたグリッド出力(output)が与えられるので、このようなoutputになる入力はいくつあるかその個数をMOD 1000000007で返す。

考え方

i行目とi+1行目について考える。


プログラムでi-1行目まではinputはoutputに置き換わっているので、outputのi行目を使えばいい。そこからinputのi+1行目がどんなWBの組み合わせが許されるか考える。
(黒,白)と(白,黒)の組み合わせは、その下の色を塗りつぶしてしまうので、そこの部分は元の色が何であれokということになる。なので、その塗りつぶされてしまう場所にWまたはBが入ってよい(2通りあり得る)。したがって、i行目からi+1行目で塗りつぶされてしまうところの数を数えればよい。


具体的には、長さがWの文字列checkなどを用意して'*'などの文字で埋めておき、i行目に応じてにBやWに置き換えたりswapする。ここで、文字列checkでBまたはWとなっているところは「何色であれ塗りつぶされる」場所なのでこの個数を調べる('*'でない部分の数)。もし、output[i+1]の文字列と文字列checkを比較して、'*'でない部分が一致しない場合は作ることができないので、0を返す。


すべての行について、塗りつぶされてしまう個数mがわかれば、そこにWまたはBが入るので、2^mの組み合わせだけあり得る。これのMOD 1000000007を取ったものが答え。