[AtCoder][ARC 081]Coloring Dominoes題解

Coloring Dominoes

時間制限:1 Secメモリ制限:128 MB原題リンクhttps://arc081.contest.atcoder.jp/tasks/ARC081_B

タイトルの説明

We have a board with a 2×N grid. Snuke covered the board with N dominoes without overlaps. Here, a domino can cover a 1×2 or 2×1 square. Then, Snuke decided to paint these dominoes using three colors: red, cyan and green. Two dominoes that are adjacent by side should be painted by different colors. Here, it is not always necessary to use all three colors. Find the number of such ways to paint the dominoes, modulo 1000000007. The arrangement of the dominoes is given to you as two strings S1 and S2 in the following manner: Each domino is represented by a different English letter (lowercase or uppercase). The j-th character in Si represents the domino that occupies the square at the i-th row from the top and j-th column from the left.
Constraints 1≤N≤52 |S1|=|S2|=N S1 and S2 consist of lowercase and uppercase English letters. S1 and S2 represent a valid arrangement of dominoes.

入力

Input is given from Standard Input in the following format: N S1 S2

しゅつりょく

Print the number of such ways to paint the dominoes, modulo 1000000007.

サンプル入力

3 aab ccb

サンプル出力

6

問題解

領域の幅は2しかなく、ドミノの骨牌ごとに連続した2つの格子しか占められないため、いずれの列に対しても2つの振り方しかなく、縦1つまたは横2つである.従って,数学的法則により塗色の可能性を算出できる.

コード#コード#

#include 
#include 

#define ull unsigned long long
#define MO 1000000007

using namespace std;
int n, k, c;
string s1, s2;
ull ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> s1 >> s2;
    if (s1[0] == s2[0])c = 1, ans = 3; else c = 2, ans = 6;
    k = c;
    while (k < n) {
        if (s1[k] == s2[k]) {
            ans *= 3 - c;
            c = 1;
        } else {
            ans *= c + 1;
            c = 2;//Skip 2
        }
        k += c;
        ans %= MO;
    }
    cout << ans;
    return 0;
}