ARC 180

Sat, Jul 5, 2025

https://atcoder.jp/contests/arc180

A. ABA and BAB

https://atcoder.jp/contests/arc180/tasks/arc180_a

自力 AC.

置換1: ABA -> A
置換2: BAB -> B

とする。

ABABA… と A, B が交互に繰り返す文字列から文字を置換すると置換1, 2のどちらを使っても同じ文字列になり、また長さが2減る。 BABABA… と B, A が交互に繰り返す文字列についても同様。

文字が交互になる長さを $M$ とする. このとき置換によって生成される文字列のパターンは $\floor{(M+1)/2}$ 通りある。

文字が交互になる区間が $L$ 個あり、$i$ 個目の区間の長さが $m_i$ のとき答えは

\begin{align*} \sum_{i=1}^{L} \floor{(m_i + 1) / 2} \mod 10^9 + 7 \end{align*}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    S.push_back(S.back());

    mint ans = 1;
    ll cnt = 1;
    char p = S[0];
    rep2(i, 1, N + 1) {
        if (p == S[i]) {
            if (cnt >= 3) ans *= (cnt + 1) / 2;
            cnt = 1;
        } else {
            cnt++;
        }
        p = S[i];
    }
    cout << ans.val() << endl;
}