　$A, B, C$ の $3$ 種類で作られる長さ $20$ の文字列の集合を $S$，$0, 1, 2$ を値にとる長さ $21$ の整数列の集合を $T$ とし，$T$ の元 $(a_0, ..., a_{20})$ であって $a_0 = 0$ をみたすものの集合を $U$ とする．また，$S$ の元を $X = (x_1, ..., x_{20})$ と表したとき，$x_k\ (1 \leq k \leq 20)$ は $X$ の $k$ 文字目を表す．ここで $S$ から $U$ への関数 $f$ を次のように定める．以後，$\equiv$ を用いた合同式における法は $3$ であるとする．

- $X = (x_1, ..., x_{20}) \in S$ に対し，$a_0 = 0$ として以下をみたす $(a_0, a_1, ..., a_{20}) \in U$ が一意的に定められるので，これを $f(X)$ とする．ただし各条件における $k$ は $1 \leq k \leq 20$ なる整数である．
  - $x_k = A$ のときは $a_k \equiv a_{k - 1} + 1$．
  - $x_k = B$ のときは $a_k \equiv a_{k - 1} - 1$．
  - $x_k = C$ のときは $a_k \equiv a_{k - 1}$．

すると $f$ は，$S$ から $U$ への全単射であることが確かめられる．また，次の補題が成り立つ．

---

**補題 1.** \
　$X = (x_1, ..., x_{20}) \in S$ と $1 \leq i \leq j \leq 20$ なる正整数 $i, j$ について以下 $2$ つは同値である．
- 文字列 $X(i, j)$ に含まれる $A, B$ の個数を $3$ で割った余りが等しい．
- $f(X) = (a_0, a_1, ..., a_{20})$ に対し $a_{i-1} = a_{j}$ が成り立つ．

<details><summary>補題 1. の証明<\/summary>
　$X(i, j)$ に含まれる $A, B$ の個数をそれぞれ $\alpha, \beta$ とすると，$f$ の定義から
$$a_j \equiv a_{i - 1} + \alpha - \beta$$
が成り立つ．特に $a_{i - 1}, a_{j} \in \\{0, 1, 2\\}$ であることに注意すればこの事実から $\alpha \equiv \beta$ と $a_{i - 1} = a_{j}$ の同値性が確かめられる．
<\/details>

---

ここで $T$ に属する列 $Y$ が次の条件をみたすとき，これを**悪い列**と呼ぶことにする．
- $Y$ に属する $0, 1, 2$ の個数をそれぞれ $C_0, C_1, C_2$ としたとき，$C_0, C_1, C_2$ の最大値は $8$ 以下である．具体的に以下 $3$ つのケースが考えられる．
  - $C_0 = C_1 = C_2 = 7$．
  - $C_0, C_1, C_2$ が $6, 7, 8$ の並び替えとなっている．
  - $C_0, C_1, C_2$ のうち $2$ つが $8$ であり，残り $1$ つが $5$ である．

すると，次の補題を得る．

---

**補題 2.** \
　$X \in S$ が問題の条件をみたすための必要十分条件は，$f(X)$ が悪い列とならないことである．

<details><summary>補題 2. の証明<\/summary>

- 必要性の証明： \
　問題の条件に適した $(i_1, i_2, ..., i_9)$ を選ぶと，$f(X) = (a_0, a_1, ..., a_{20})$ としたときに $a_{i_1} = a_{i_2} = \cdots = a_{i_9}$ であることが，補題 1. によって確かめられる．これは $f(X)$ の中に同一の数が $9$ つ以上含まれることを意味するので，$f(X)$ は悪い列ではない．

- 十分性の証明： \
　$f(X) = (a_0, a_1, ..., a_{20})$ が悪い列でないとすると，
$$0 \leq i_1 \lt i_2 \lt \cdots \lt i_9 \leq 20，a_{i_1} = a_{i_2} = \cdots = a_{i_9}$$ 
をともにみたす $9$ 個の整数の組 $(i_1, i_2, ..., i_9)$ を得ることができる．補題 1. から $8$ つの文字列
$$X(i_1 + 1, i_2)，X(i_2 + 1, i_3)，...，X(i_8 + 1, i_9)$$
はすべて，それぞれに含まれる $A, B$ の個数の $3$ で割った余りが一致する．すなわち $X$ は問題の条件をみたす．
<\/details>

---

　補題 2. より，$U$ に含まれる悪い列でない列の個数を求めればよい．まずは $T$ に含まれる悪い列の個数を求めよう．悪い列の定義のときに挙げた $3$ 通りのケースでそれぞれ個数を求めると
$$\frac{21!}{7!^3}，\frac{21!}{6!7!8!} \times 6，\frac{21!}{5!8!^2} \times 3$$

であり，全体の個数はこれらの和によって求められる．また，$Y \in T$ とし，$Y$ の各項を $0 \rightarrow 1 \rightarrow 2 \rightarrow 0$ と循環して置き換えたものを $Z$ とすると，$Y$ が悪い列のとき，かつそのときに限り $Z$ も悪い列となる．したがって，$U$ に含まれる悪い列の個数を $N$ としたとき
$$3N = \frac{21!}{7!^3} + \frac{21!}{6!7!8!} \times 6 + \frac{21!}{5!8!^2} \times 3$$
が成り立つので，これより
$$N = \frac{2 \cdot 263 \cdot 21!}{3 \cdot 7! 8!^2}$$
を得る．$N$ は明らかに $2, 3, 5, 7, 11, 13, 17, 19, 263$ 以外の素数で割り切れない．素数 $p$ に対し $N$ を $p$ で割り切る最大の回数を $v_p$ と表すと，Legendre の公式を用いるなどすることで
$$v_2 = v_5 = v_{11} = v_{13} = v_{17} = v_{19} = v_{263} = 1，v_3 = 2，v_7 = 0$$
が確かめられる．したがって
$$N = 2 \times 3^2 \times 5 \times 11 \times 13 \times 17 \times 19 \times 263$$
である．$U$ に含まれる列は全部で $3^{20}$ 個あるので，求める個数は
$$3^{20} - N = \mathbf{2393490771}$$
である．
公式解説
https://onlinemathcontest.com/contests/omc204/editorial/9456
　長さ $20$ の文字列 $X$ は $A, B, C$ の $3$ 種類の文字からなります（ただし，一度も使わない文字の種類があっても構いません）．ここで，$1 \leq i \leq j \leq 20$ なる整数 $i, j$ に対し，$X$ の $i$ 文字目から $j$ 文字目までを切り取った（長さ $j - i + 1$ の）文字列を $X(i, j)$ と表します．このとき，次の条件をみたす $X$ は全部でいくつありますか？

- ある $0 \leq i_1 \lt i_2 \lt \cdots \lt i_9 \leq 20$ なる $9$ 個の整数の組 $(i_1, i_2, \ldots, i_9)$ が存在して，$1 \leq k \leq 8$ なる任意の整数 $k$ について，文字列 $X(i_k + 1, i_{k+1})$ に含まれる $A, B$ の個数の差が $3$ の倍数となる．

<details><summary>$X(i, j)$ の例<\/summary>
　たとえば文字列 $X$ が
$$BBCAACBCAABBAACABBAC$$
と表されるとき，$X(3, 7), X(10, 15), X(1, 1)$ はそれぞれ
$$CAACB, \quad ABBAAC, \quad B$$
です．
<\/details>