SRM 504 medium AlgridTwo

topcoder

問題概要

黒か白かにぬられた表がある。
上の段の二つのセルの状態からそのすぐ下の段の二つの色を塗りつぶしたり
入れ替えたりする。
全ての段に対してその処理を行ったデータが与えられる。
その出力になりうる入力の種類数を答えよ。

解法

何色でも構わないマスの数を数え上げて
その数で2を累乗する。
上の段に従って実際に下の段（なにも色を塗ってない状態で）入れ替えたり塗りつぶしたりしてみる。
上の段の操作で塗りつぶされたセルはもともとどんな色であっても結果が変わらないので
その数を数える。
上の段から得られたセルの情報でセルの色が確定されている場所で
与えられた出力と一致しないならば、そのような出力になる入力は存在しないので、
0を返す.

ソース

const lli MOD = 1000000007;
lli solve(string s1, string s2){
  int W = s1.length();
  string tmp(W, '?');
  rep(i, W-1){
    if(s1[i] == 'B' && s1[i+1] == 'W'){
      tmp[i] = tmp[i+1] = 'B';
    }
    else if(s1[i] == 'W' && s1[i+1] == 'B'){
      tmp[i] = tmp[i+1] = 'W';
    }
    else if(s1[i] == 'B' && s1[i+1] == 'B'){
      swap(tmp[i], tmp[i+1]);
    }
  }
  rep(i, W){
    if(tmp[i] == '?')continue;
    if(tmp[i] != s2[i])return 0;
  }
  lli res = 1;
  rep(i, W){
    if(tmp[i] != '?'){
      res *= 2;
      res %= MOD;
    }
  }
  return res;
}

class AlgridTwo {
public:
  int makeProgram(vector <string> output) {
    lli result = 1;
    int n = output.size();
    rep(i, n-1){
      result *= solve(output[i], output[i+1]);
      result %= MOD;
    }
    return result;
  }

  

};