526互联

abc071d <递推>

发布时间 2023-07-10 16:56:16作者: O2iginal

D - Coloring Dominoes

// https://atcoder.jp/contests/abc071/tasks/arc081_b
// <递推>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 60, mod = 1e9 + 7;
char s[2][60];


void solv()
{
    int n;
    cin >> n;
    cin >> (s[0] + 1) >> (s[1] + 1);
    LL ans;
    int last = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (s[0][i] == s[1][i])  // now = 1
        {
            if (last == 0) ans = 3;
            else if (last == 1) ans = ans * 2 % mod;
            last = 1;
        }
        else  // now = 2
        {
            if (last == 0) ans = 6;
            else if (last == 1) ans = ans * 2 % mod;
            else ans = ans * 3 % mod;
            i ++;
            last = 2;
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}