ABC071 D - Coloring Dominoes

問題
提出コード

解法

縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くときに、番目の文字ではなく番目の文字を見るようにしておきます。
この問題では、左から順番に見ていくと、セット目のドミノについて、セット目のドミノ以外は色の付け方に影響がありません。番目より手前のドミノは番目の色の付け方とは無関係です。
ので、左から順番に見ていくだけで答えを求めることができます。
まず、一番左のセットについての塗り方を考えると、

• 縦のセット:3通り

• 横のセット:6通り

となります。
次に、セット目のドミノの色の付け方を考えます。
と番目がどのセットになっているかによるので、4通り存在します。

• 番目が縦、番目も縦:番目までの塗り方の2倍です。

• 番目が縦、番目が横:番目までの塗り方の2倍です。

• 番目が横、番目が縦:番目までの塗り方のままです。

• 番目が横、番目も横:番目までの塗り方の3倍です。

というようにして、番目までの色の付け方を1~3倍していくことで、最終的に最後のドミノまでの色の付け方を求めることができます。
あとは、modをとり忘れないようにしつつ、計算していけば答えを求めることができます。