ARC081 D - Coloring Dominoes

問題

2 * Nのマス目に1 * 2のタイルを敷き詰めていく。そしてこのタイルに隣り合ったタイル通し同じ色にならないように3色の色を塗って行きたい。何通りの塗り方があるか。

解法

この問題のタイルの配置の種類は以下の画像の4通りしかない。

左隣のブロックの配色が決まっている時、その右隣の色の塗りかたは、Aは2通り、Bは3通り、Cは1通り、Dは2通りとなるので、これを元に実装していけばいい。

ソースコード

const int mod = 1000000007;

int main(){
  int N;
  string s[2];
  cin >> N >> s[0] >> s[1];

  long long ans = (s[0][0] == s[1][0] ? 3 : 6);
  for(int i = 1; i < (int)s[0].size(); i++){
    if(s[0][i] == s[0][i - 1]) continue;
    
    if(s[0][i] == s[1][i]){
      if(s[0][i - 1] == s[1][i - 1]) ans = (ans * 2) % mod;
      else ans *= 1;
    }else{
      if(s[0][i - 1] == s[1][i - 1]) ans = (ans * 2) % mod;
      else ans = (ans * 3) % mod;
    }
  }
  cout << ans << endl;
  return 0;
}