OMC230(F) - 文字の巡回に注目する

　$3$ 種類の文字に対する $2$ 通りの巡回（$ABCABCA ...$ か $ACBACBA ...$）に注目し，操作を繰り返した後の文字列がどのような形になるのかを調べる解法です．

　$A, B, C$ からなり，なおかつ同じ文字が隣接しないような文字列のことをここでは良い文字列と呼ぶことにする．長さ $L$ の良い文字列 $S$ に対し，次のルールにしたがって作られる長さ $L - 1$ の $X, Y$ からなる文字列を $f(S)$ と表そう．

• 各 $k = 1, ..., L - 1$ に対し，$k, k + 1$ 文字目の連続 $2$ 文字が $AB, BC, CA$ のいずれかであれば $k$ 文字目を $X$ とし，$AC, CB, BA$ のいずれかであれば $k$ 文字目を $Y$ とする．

つまり $ABCABCA ...$ という巡回が起きるときに $X$，$ACBACBA ...$ という巡回が起きるときに $Y$ が設定されるようなイメージである．たとえば， $$f(ABACA) = XYYX，f(ABCACAB) = XXXYXX$$ などが成り立つ．ここで次の事実を得る．

• 事実 1.　$S$ を良い文字列とし，$S$ に対し問題の操作を $1$ 回施して得られる良い文字列を $S^{\prime}$ とする．このとき $f(S)$ に対し $$X \rightarrow YY，Y \rightarrow XX$$ の置き換えをすべて同時に施すと，$f(S^{\prime})$ が得られる（それぞれの巡回が逆向きとなり倍増するイメージ）．

　それでは長さ $2023$ の良い文字列 $S_0$ に対し，操作を $2023$ 回繰り返して得られる文字列を $S_1$ としよう．また，$g(k) = 2^{2023} (k - 1) + 1$ とする．このとき $S_0$ の選び方によらず以下 $2$ つが成り立つ（事実 3. は事実 1. からしたがう）．

• 事実 2.　各 $k = 1, ..., 2023$ に対し，$S_0$ の $k$ 文字目と $S_1$ の $g(k)$ 文字目は等しい．
• 事実 3.　任意の $k = 1, ..., 2022$ について，$f(S_1)$ の $g(k)$ 文字目から $g(k + 1) - 1$ 文字目までの $2^{2023}$ 文字は，すべて $X$ であるか，すべて $Y$ である．

ここで $2^{2023} \equiv 2 \pmod{3}$ に注意し，$\alpha = \dfrac{2^{2023} + 1}{3}$ とおこう．各 $k = 1, ..., 2022$ に対し，$S_1$ の $g(k)$ 文字目から $g(k + 1)$ 文字目までの $2^{2023} + 1\ (= 3 \alpha)$ 文字は，$ABCABC ... ABC$ などのように同じ $3$ 文字を $\alpha$ 回繰り返していることが事実 3. からわかり，特に $C$ はこの範囲にちょうど $\alpha$ 個含まれる．このことをすべての $k$ について適用しよう．すると，$S_1$ の $g(2), g(3), ..., g(2022)$ 文字目の中に含まれる $C$ の個数を $x$，$S_1$ 全体に含まれる $C$ の個数を $y$ と表したとき， $$x + y = 2022 \alpha$$ が成り立つ．また，事実 2. より $x$ は $S_0$ における $2$ 文字目から $2022$ 文字目までに含まれる $C$ の個数に等しい．$S_0$ が良い文字列であることから $x$ のとり得る範囲は $0 \leq x \leq 1011$ なので，結局 $y$ の最大値 $M$ と最小値 $N$ はそれぞれ以下のように表せる． $$M = 2022 \alpha，N = 2022 \alpha - 1011$$ $x = 0$ なる $S_0$ は $2$ 文字目から $2022$ 文字目までが $ABABA ... ABA$ か $BABAB ... BAB$ のどちらかであり，それぞれに対し $1$ 文字目と $2023$ 文字目を決める方法は $2$ 通りずつある．よって，$m = 2^3 = 8$ を得る．$x = 1011$ なる $S_0$ の場合は偶数文字目をすべて $C$ にする他なく，残りの $1012$ 個の文字をそれぞれ独立に $A, B$ のどちらかに定めればよい．よって，$n = 2^{1012}$ を得る．あとは公式解説同様 $M + m + N + n$ を $503$ で割った余りを求めればよい．