概要

A, B, C からなる文字列 \(S\) の C を A/B に置き換えて、AA という連続部分文字列を含まない文字列を作る方法の総数を \(998244353\) で割った余りを求める問題です。典型的な「直前の文字の状態を持つ桁DP（線形DP）」で解けます。

考察

素朴なアプローチ

C の個数を \(k\) とすると、全部の置き換え方は \(2^k\) 通りです。\(k\) は最大 \(2 \times 10^6\) になり得るので、全列挙は当然不可能（\(2^{2000000}\) 通り）です。したがって数え上げを工夫する必要があります。

重要な気づき

禁止条件は「AA が現れない」という 隣り合う 2 文字だけの条件 です。つまり、\(i\) 日目の文字を決めるときに知っておく必要がある情報は

\(i-1\) 日目の文字が A だったか B だったか

だけです。それより前の文字がどうだったかは、\(i\) 日目以降の可否には一切影響しません。

この「必要な情報が直前 1 文字分だけ」という性質から、動的計画法（DP）で

• \(\mathrm{dpA}[i]\)：\(i\) 日目までを決め、かつ \(i\) 日目が A であるような、条件を満たす決め方の個数
• \(\mathrm{dpB}[i]\)：\(i\) 日目までを決め、かつ \(i\) 日目が B であるような、条件を満たす決め方の個数

という 2 つの値を管理すれば、\(O(N)\) で総数が求まります。同じ「末尾の文字」を持つ状態をひとまとめに数え上げることで、指数時間を線形時間に落としているわけです。

遷移の考え方

\(i\) 日目に A を置く場合、\(i-1\) 日目は B でなければなりません（A だと AA になる）。よって

\[\mathrm{dpA}[i] = \mathrm{dpB}[i-1]\]

\(i\) 日目に B を置く場合、\(i-1\) 日目は A でも B でも構いません。よって

\[\mathrm{dpB}[i] = \mathrm{dpA}[i-1] + \mathrm{dpB}[i-1]\]

ただし、\(S_i\) が A なら \(i\) 日目に B は置けず（\(\mathrm{dpB}[i]=0\)）、B なら A は置けません（\(\mathrm{dpA}[i]=0\)）。C のときだけ両方の遷移を使います。

具体例

\(S = \) ACA の場合。

• \(i=1\)：\(S_1 = \) A なので \(\mathrm{dpA}=1, \mathrm{dpB}=0\)。
• \(i=2\)：\(S_2 = \) C なので両方試す。
  • A を置く → \(\mathrm{dpA}[2] = \mathrm{dpB}[1] = 0\)（AA になるのでダメ）
  • B を置く → \(\mathrm{dpB}[2] = 1 + 0 = 1\)
• \(i=3\)：\(S_3 = \) A なので A のみ。
  • \(\mathrm{dpA}[3] = \mathrm{dpB}[2] = 1\)、\(\mathrm{dpB}[3] = 0\)

答えは \(1 + 0 = 1\)（ABA のみ）。

なお、\(S\) にもともと AA が含まれる場合（例：\(S=\) AA）は、遷移の途中で両方の値が \(0\) になり、自動的に答えが \(0\) になります。特別扱いは不要です。

アルゴリズム

1. 1 日目を処理して初期値を作る。
   • \(S_1 = \) A → \((\mathrm{dpA}, \mathrm{dpB}) = (1, 0)\)
   • \(S_1 = \) B → \((0, 1)\)
   • \(S_1 = \) C → \((1, 1)\)
2. \(i = 2, 3, \dots, N\) について次を計算する（新しい値を \(nA, nB\) とし、初期値 \(0\)）。
   • \(S_i \in \{\)A, C\(\}\) のとき：\(nA \gets \mathrm{dpB}\)
   • \(S_i \in \{\)B, C\(\}\) のとき：\(nB \gets (\mathrm{dpA} + \mathrm{dpB}) \bmod 998244353\)
   • \((\mathrm{dpA}, \mathrm{dpB}) \gets (nA, nB)\)
3. 答えは \((\mathrm{dpA} + \mathrm{dpB}) \bmod 998244353\)。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力文字列の格納分。DP 自体は \(O(1)\)）

実装のポイント

• 配列を持たず 2 変数で回す：\(\mathrm{dp}[i]\) は \(\mathrm{dp}[i-1]\) のみに依存するので、長さ \(N\) の配列は不要です。\(N \le 2\times 10^6\) なので配列でも通りますが、変数 2 つの方がメモリにも定数倍にも優しいです。

• 更新順序に注意：\(\mathrm{dpA}\) を先に上書きすると \(\mathrm{dpB}\) の計算に古い \(\mathrm{dpA}\) が使えなくなります。必ず新しい値を一時変数 \(nA, nB\) に入れてから同時に代入しましょう。

• 毎回 % を取る：\(\mathrm{dpA}+\mathrm{dpB}\) は最大でも \(2 \times (\text{MOD}-1)\) 程度なので long long（あるいは int でも工夫すれば）でオーバーフローしませんが、必ず MOD を取って値を \([0, \text{MOD})\) に保ちます。

• 高速な入力：\(N\) が \(2\times 10^6\) と大きいので、C++ では scanf／std::cin + sync_with_stdio(false) などを使い、Python なら sys.stdin から読むようにしましょう。文字列を 1 文字ずつ遅い方法で読むと TLE の危険があります。

• \(N = 1\) のケースでは初期値をそのまま足して出力するだけで正しく動きます（C なら答え \(2\)）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main(){
    int n;
    scanf("%d", &n);
    static char buf[2000006];
    scanf("%s", buf);
    string s(buf);
    // dpA: ways ending with A, dpB: ways ending with B
    long long dpA = 0, dpB = 0;
    // first char
    if(s[0]=='A'){dpA=1;dpB=0;}
    else if(s[0]=='B'){dpA=0;dpB=1;}
    else {dpA=1;dpB=1;}
    for(int i=1;i<n;i++){
        long long nA=0,nB=0;
        char c=s[i];
        if(c=='A'||c=='C') nA = dpB;
        if(c=='B'||c=='C') nB = (dpA+dpB)%MOD;
        dpA=nA;dpB=nB;
    }
    printf("%lld\n", (dpA+dpB)%MOD);
    return 0;
}

---

この解説は claude5opus-high によって生成されました。