ABC-071-D Coloring Dominoes

■■■問題■■■

2×Nのマス目があります。
すぬけ君は、このマス目にN個のドミノを、重ならないように敷き詰めました。
ここで、ドミノは、1×2または2×1のマス目を覆うことができます。

すぬけ君は、赤色、水色、緑色の3色を使って、これらのドミノを塗ることにしました。
このとき、辺で接しているドミノは異なる色で塗るようにします。
ここで、必ずしも3色すべてを使う必要はありません。

このような塗り方が何通りあるかを mod 1000000007 で求めてください。

ただし、ドミノの敷き詰め方は、文字列S1,S2を用いて、次のようにして与えられます。
●各ドミノは、それぞれ異なる英小文字または英大文字で表される。
●Siのj文字目は、マス目の上からi番目、左からj番目のマスにどのドミノがあるかを表す。

■■■入力■■■

N
S1
S2

●1 <= N <= 52
●|S1| = |S2| = N
●S1,S2 は英小文字または英大文字からなる
●S1,S2 は正しいドミノの敷き詰め方を表している

■■■出力■■■

ドミノを塗る方法の数を mod 1000000007 で出力せよ。

■■■サンプルケースのイメージ■■■

■入出力例1のイメージ■
次の6通りあります

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("aab");
            WillReturn.Add("ccb");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            WillReturn.Add("Z");
            WillReturn.Add("Z");
            //3
            //必ずしもすべての色を使わなくてもよいことに注意してください
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("52");
            WillReturn.Add("RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn");
            WillReturn.Add("RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn");
            //958681902
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S1 = InputList[1];
        string S2 = InputList[2];

        int UB_X = S1.Length - 1;
        int UB_Y = 1;

        char[,] BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (LoopY == 0) BanArr[LoopX, 0] = S1[LoopX];
                if (LoopY == 1) BanArr[LoopX, 1] = S2[LoopX];
            }
        }

        //横に配置をX、縦に配置をY、として文字列で持つ
        var HaitiList = new List<char>();
        for (int LoopX = 0; LoopX <= UB_X; ) {
            if (BanArr[LoopX, 0] != BanArr[LoopX, 1]) {
                HaitiList.Add('X');
                LoopX += 2;
            }
            else {
                HaitiList.Add('Y');
                LoopX++;
            }
        }

        long Answer = 1;
        for (int I = 0; I <= HaitiList.Count - 1; I++) {
            char CurrHaiti = HaitiList[I];

            if (I == 0) {
                Answer = (CurrHaiti == 'X' ? 6 : 3);
            }
            else {
                char PrevHaiti = HaitiList[I - 1];
                if (PrevHaiti == 'X' && CurrHaiti == 'X') Answer *= 3;
                if (PrevHaiti == 'X' && CurrHaiti == 'Y') Answer *= 1;
                if (PrevHaiti == 'Y' && CurrHaiti == 'X') Answer *= 2;
                if (PrevHaiti == 'Y' && CurrHaiti == 'Y') Answer *= 2;
            }
            Answer %= 1000000007;
        }
        Console.WriteLine(Answer);
    }
}

解説

ドミノを横に配置するならX
ドミノを縦に配置するならY
として、配置の仕方を求めておき、
1番左から配置ごとの場合の数で、積の法則を使ってます。