　$S$ を問題の総和とする．また，以下では合同式の法は $3$ であるとし，$x_{10+k}=x_{k}, y_{10+k}=y_{k}$ となるように $x_{11}, y_{11}, x_{12}, y_{12}, \dots$ を定める．

　$A= \\{ (1,3), (3,1), (1,1), (3,3), (2,2) \\}$，$B = \\{ (2,1), (1,2), (2,3), (3,2) \\}$ とおく．$(a,b) \in A$ であるとき，$a^y + y^b \bmod{3}$ を $y=4,5,6$ に対して計算すると，順に
- $1^y + y^3 \equiv 2,0,1$ 
- $3^y + y^1 \equiv 1,2,0$ 
- $1^y + y^1 \equiv 2,0,1$ 
- $3^y + y^3 \equiv 1,2,0$ 
- $2^y + y^2 \equiv 2,0,1$ 

なので，いずれの場合も $0,1,2$ がちょうど $1$ 回ずつ現れることがわかる．


**Case 1.** $X = (x_1,\dots, x_{10})$ について「$(x_1, x_2), (x_2, x_3),  \dots  (x_{9}, x_{10}), (x_{10}, x_{1})$ の中に $A$ の要素が少なくとも一つ含まれている」ことを仮定する．その $A$ の要素の一つを $(x_{i}, x_{i+1})$ とおく．このとき $S$ の中の $x_i^{y_i} + y_{i}^{x_{i+1}}$ を見ることで，$y_{i}$ を除く $y_1,y_2,y_3,\dots, y_{10}$ の値を $3^{9}$ 通りの中からどのように決めたとしても，ちょうど一つの $y_{i} \in \\{ 4,5,6\\}$ が存在して $S\equiv 0$ にすることができる．\
　したがって，この仮定を満たす $(x_1,x_2,\dots, x_{10})$ が $N$ 個あるとするとき，条件を満たす列の組 $(X,Y)$ が $3^9\cdot N$ 個得られる．

**Case 2.** $X = (x_1,\dots, x_{10})$ について，$(x_1, x_2), (x_2,x_3),  \dots  (x_{9}, x_{10}), (x_{10}, x_{1})\in B$ である場合を考える．このような $X$ は，$k_{i} \in \\{ 1,3\\}$ を用いて 
$$
(2,k_2,2,k_4,2,k_6,2,k_8,2,k_{10}),\quad (k_1,2,k_3,2,k_5,2,k_7,2,k_9,2) 
$$
と表せるような $64$ 組のいずれかであることが分かるから，$3^{10} - N = 64$ である．よって $N = 3^{10} - 64$ である． 

　$X = (k_1,2,k_3,2,k_5,2,k_7,2,k_9,2)$ の場合を考える．$k_{1}, k_3, k_5, k_7, k_9\in \\{ 1, 3\\} $ なので 
$$
\begin{aligned}
y_{2i-1}^{k_{2i-1}} + k_{2i-1}^{y_{2i}} + y_{2i}^{2} + 2^{y_{2i+1}} \equiv y_{2i-1} + k_{2i-1} + y_{2i}^2 + 2^{y_{2i+1}}
\end{aligned}
$$
が $i=1,2,3,4,5$ で成り立つ．したがって，
$$
\begin{aligned}
S &\equiv \sum_{i=1}^{5}(2^{y_{2i-1}} + y_{2i-1}) + \sum_{i=1}^{5} y_{2i}^2 + \sum_{i=1}^{5} k_{2i-1}  \\\\ 
\end{aligned}
$$
となる．この式から $S\equiv 0$ となるための $y_1,\dots, y_{10}, k_{1}, k_{3}, \dots, k_{10}$ の条件を考える．

　$y=4,5,6$ のとき $2^y + y \equiv 2,1,1$ および $x^2 \equiv 1,1,0$ である．したがって，$S\equiv 0$ となる $(y_1,y_2,\dots, y_{10}, k_{1}, \dots, k_{5})$  の個数を求めることは，次の場合の数を求めることに帰着する．

-  $\\{ 1,1,2\\}, \\{ 0,1,1 \\}, \\{ 0,1 \\} $ がそれぞれ $5$ 個ずつ，計 $15$ 個の多重集合がある．これら $15$ 個から 要素を一つずつ選ぶ．選んだ要素の和が $3$ の倍数になるような選び方はいくつあるか．

これは多項式 $f(x) = (2x + x^2)^5(1 + 2x)^5(1 + x)^5$ の $x^{3n}$ $(n=0,1,2,\dots)$ の係数の総和として求められ，$\omega = \dfrac{-1 + \sqrt{-3}}{2}$ とおくと $\displaystyle \frac{1}{3} \sum_{k=0}^{2} f(\omega^{k})$ に等しい．$f(x) = (2x^4 + 7x^3 + 7x^2 + 2x)^5$ より，
$$
\begin{aligned}
&\dfrac{1}{3} \sum_{x=1, \omega, \omega^2} (2x^4 + 7x^3 + 7x^2 + 2x)^5 \\\\
&= \dfrac{1}{3} \sum_{x=1, \omega, \omega^2} (7x^3 + 7x^2 + 4x)^5 \\\\
&= \dfrac{1}{3} \cdot 18^{5} + \dfrac{1}{3}\sum_{x=\omega, \omega^2} (7x^3 + 7x^2 + 4x)^5 \\\\ 
&= 6\cdot 18^{4} + \dfrac{1}{3}\sum_{x=\omega, \omega^2} (-3x)^5 \\\\
&= 6\cdot 18^4 - 3^4\cdot (\omega^5 + \omega^{10}) \\\\
&= 6\cdot 18^4 + 81
\end{aligned}
$$
$x_1,x_2,\dots, x_{10}$ の役割は巡回的に対称なので，$X = (2,k_2,2,k_4,2,k_6,2,k_8,2,k_{10})$ の場合も同様である．したがって **Case 2.** の場合は $12 \cdot 18^{4} + 162$ 組 の条件を満たす $(X,Y)$ が得られる．

　以上より，求める個数は
$$
3^{9}\cdot (3^{10} - 64) + (12 \cdot 18^{4} +162) = 3^{19} + 162 = \mathbf{1162261629}
$$
公式解説
https://onlinemathcontest.com/contests/nfhai2024/editorial/12400
　$a^b$ の $\mathrm{mod} ~ 3$ における寄与を考えるとき, $b$ が偶数か奇数かで性質が変わってしまう. よって, 
$$x_1\rightarrow y_{10}\rightarrow x_{10}\rightarrow\cdots\rightarrow y_1$$ の順に決めながら, 直前に決めた数の偶奇で場合分けを行い,
$$ y_{10}^ {x_1}\rightarrow x_{10}^{y_{10}}\rightarrow y_{9}^{x_{10}}\rightarrow\cdots\rightarrow x_1^{y_1} $$
の順に寄与を反映させる. \
また最初に決めた $x_1$ の値で, 最後の $x_1^{y_1}$ の寄与も依存するから最初に決める $x_1$ の偶奇で場合分けをする. 

---

　① $x_1\in \\{1,3\\}$ のとき.\
多項式 ( $3$ で割った余りが同じ次数は同一視, すなわち $x^3-1$ を法として考える) $f(x),g(x)$ を以下のように定義する. 

- $Z=(x_1,y_{10}),\\;\ S=y_{10}^{x_1}$ とし, $Z$ の末尾の要素 を $2$ で割った余りが $i$ で, $S$ を $3$ で割った余りが $j$ となる $Z$ の個数を $dp[i][j]$ とし,
$$f(x)=dp[0][0]+dp[0][1]x+dp[0][2]x^2,\quad g(x)=dp[1][0]+dp[1][1]x+dp[1][2]x^2$$
とする.

　このとき, 初期値として,
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}=
\begin{pmatrix}
1+x\\\\
x^2\\\\
\end{pmatrix}
$$
が成り立つ. $Z\leftarrow (Z,x_{10}),\\;\ S\leftarrow S+x_{10}^{y_{10}}$ とし, このとき $f,g$ は以下のように変化する.
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}
\leftarrow 
\begin{pmatrix}
x&x^2\\\\
1+x&1+x\\\\
\end{pmatrix}
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}$$
次に, $Z\leftarrow (Z,y_9),\\;\ S\leftarrow S+y_9^{x_{10}}$ のときの $(f,g)$ の遷移は
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}
\leftarrow 
\begin{pmatrix}
1+x&1+x\\\\
x&x^2\\\\
\end{pmatrix}
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}$$
となる. 従って, 初期値 $Z=(x_1,y_{10}),\\;\ S=y_{10}^{x_1}$ から 
$$Z\leftarrow (Z,x_{10},y_9,x_9,\dots,y_1),\\;S\leftarrow S+x_{10}^{y_{10}}+y_9^{x_{10}}+x_9^{y_9}+\cdots+y_1^{x_2}$$
 における $(f,g)$ の遷移は
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}
\leftarrow 
\Bigg(
\begin{pmatrix}
1+x&1+x\\\\
x&x^2\\\\
\end{pmatrix}
\begin{pmatrix}
x&x^2\\\\
1+x&1+x\\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}$$
であり, この状態から最後 $Z\leftarrow (Z,x_1), S\leftarrow S+x_1^{y_1}$ としたときの遷移は $x_1\in\\{1,3\\}$ に注意すると,
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}
\leftarrow 
\begin{pmatrix}
0&0\\\\
1+x&1+x\\\\
\end{pmatrix}
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}$$
となる. したがって, 以下の多項式 $f(x),g(x)$ それぞれの $3$ の倍数次の項の係数の総和を求めれば良い.
$$
\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}=
\begin{pmatrix}
0&0\\\\
1+x&1+x\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
1+x&1+x\\\\
x&x^2\\\\
\end{pmatrix}
\begin{pmatrix}
x&x^2\\\\
1+x&1+x\\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
1+x\\\\
x^2\\\\
\end{pmatrix}$$
上式に $x=1,\omega,\omega^2$ を代入すると,
$$
\begin{aligned}
\begin{pmatrix}
f(1)\\\\
g(1)\\\\
\end{pmatrix}&=
\begin{pmatrix}
0&0\\\\
2&2\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
2&2\\\\
1&1\\\\
\end{pmatrix}
\begin{pmatrix}
1&1\\\\
2&2\\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
2\\\\
1\\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
0&0\\\\
2&2\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
6&6\\\\
3&3\\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
2\\\\
1\\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
0&0\\\\
2&2\\\\
\end{pmatrix}
3^9
\begin{pmatrix}
2&2\\\\
1&1\\\\
\end{pmatrix}^9
\begin{pmatrix}
2\\\\
1\\\\
\end{pmatrix}
\\\\
&=
\begin{pmatrix}
0&0\\\\
2&2\\\\
\end{pmatrix}
3^9\times 3^8
\begin{pmatrix}
2&2\\\\
1&1\\\\
\end{pmatrix}
\begin{pmatrix}
2\\\\
1\\\\
\end{pmatrix}\\\\
&=\begin{pmatrix}
0\\\\
18\times 3^{17}\\\\
\end{pmatrix}\\\\
\begin{pmatrix}
f(\omega)\\\\
g(\omega)\\\\
\end{pmatrix}&=
\begin{pmatrix}
0&0\\\\
1+\omega &1+\omega\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
1+\omega &1+\omega\\\\
\omega &\omega^2 \\\\
\end{pmatrix}
\begin{pmatrix}
\omega &\omega^2 \\\\
1+\omega &1+\omega \\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
1+\omega \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=\begin{pmatrix}
0&0\\\\
\- \omega^ 2 &\- \omega^ 2\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
\- \omega^ 2 &\- \omega^ 2\\\\
\omega &\omega^2 \\\\
\end{pmatrix}
\begin{pmatrix}
\omega &\omega^2 \\\\
\- \omega^ 2 &\- \omega^ 2 \\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
\- \omega^2 \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=\begin{pmatrix}
0&0\\\\
\- \omega^ 2 &\- \omega^ 2\\\\
\end{pmatrix}
\begin{pmatrix}
\- 1+\omega &0 \\\\
\omega^2 \- \omega &1\- \omega \\\\
\end{pmatrix}^9
\begin{pmatrix}
\- \omega^2 \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
0&0\\\\
\- \omega^ 2 &\- \omega^ 2\\\\
\end{pmatrix}
(-1+\omega)^9
\begin{pmatrix}
1 &0 \\\\
\omega & -1 \\\\
\end{pmatrix}^9
\begin{pmatrix}
\- \omega^2 \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=\begin{pmatrix}
0&0\\\\
\- \omega^ 2 &\- \omega^ 2\\\\
\end{pmatrix}
\Big(\sqrt{3}\exp\Big(\frac{5}{6}\pi i \Big)\Big)^9
\begin{pmatrix}
1 &0 \\\\
\omega & -1 \\\\
\end{pmatrix}^9
\begin{pmatrix}
\- \omega^2 \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=\begin{pmatrix}
0&0\\\\
\- \omega^ 2 &\- \omega^ 2\\\\
\end{pmatrix}
\sqrt{3^9}(-i)
\begin{pmatrix}
1 &0 \\\\
\omega & -1 \\\\
\end{pmatrix}
\begin{pmatrix}
\- \omega^2 \\\\
\omega^2 \\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
0\\\\
\dfrac{3^5+3\sqrt{3^9}i}{2}\\\\
\end{pmatrix}\\\\
\begin{pmatrix}
f(\omega^2)\\\\
g(\omega^2)\\\\
\end{pmatrix}&=
\begin{pmatrix}
\overline{f(\omega)}\\\\
\overline{g(\omega)}\\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
0\\\\
\dfrac{3^5-3\sqrt{3^9}i}{2}\\\\
\end{pmatrix}
\end{aligned}$$
したがって, ①の場合求める組の個数は 
$$\frac{1}{3}\Big(18\times 3^{17}+\dfrac{3^5+3\sqrt{3^9}i}{2}+\dfrac{3^5-3\sqrt{3^9}i}{2}\Big)=18\times 3^{16}+3^4$$ である.

　②$x_1\in \\{2\\}$ のとき.\
①と同様に行うが初期値と最後の遷移が違うことに注意すると, 答えは以下の多項式 $f(x),g(x)$ それぞれの $3$ の倍数次の項の係数の総和であることがわかる.
$$\begin{pmatrix}
f(x)\\\\
g(x)\\\\
\end{pmatrix}=
\begin{pmatrix}
x&x^2\\\\
0&0\\\\
\end{pmatrix}
\Bigg(
\begin{pmatrix}
1+x&1+x\\\\
x&x^2\\\\
\end{pmatrix}
\begin{pmatrix}
x&x^2\\\\
1+x&1+x\\\\
\end{pmatrix}
\Bigg)^9
\begin{pmatrix}
1+x\\\\
x\\\\
\end{pmatrix}$$
①と同様に計算すると,
$$
\begin{aligned}
\begin{pmatrix}
f(1)\\\\
g(1)\\\\
\end{pmatrix}&
=
\begin{pmatrix}
9\times 3^{17}\\\\
0\\\\
\end{pmatrix}\\\\
\begin{pmatrix}
f(\omega)\\\\
g(\omega)\\\\
\end{pmatrix}&
=\begin{pmatrix}
\dfrac{3^5+3\sqrt{3^9}i}{2}\\\\
0\\\\
\end{pmatrix}\\\\
\begin{pmatrix}
f(\omega^2)\\\\
g(\omega^2)\\\\
\end{pmatrix}&
=\begin{pmatrix}
\dfrac{3^5-3\sqrt{3^9}i}{2}\\\\
0\\\\
\end{pmatrix}\\\\
\end{aligned}
$$
したがって, ②の場合求める組の個数は, $9\times 3^{16}+3^4$ である.

以上より, 求める答えは
$$(18\times 3^{16}+3^4)+(9\times 3^{16}+3^4)=27\times 3^{16}+2\times 3^4.$$
2つの母関数(多項式)を用いる解法
https://onlinemathcontest.com/contests/nfhai2024/editorial/12400/705
　各項が $1$ 以上 $3$ 以下の整数列 $X=(x_1,x_2,\dots, x_{10})$ と，各項が $4$ 以上 $6$ 以下の整数列 $Y=(y_1,y_2,\dots, y_{10})$ の組 $(X,Y)$ であって，
$$
x_{1}^{y_1} + y_1^{x_2} + x_2^{y_2} + y_2^{x_3} +  \dots + x_9^{y_9} +y_{9}^{x_{10}} + x_{10}^{y_{10}} + y_{10}^{x_{1}}
$$
が $3$ の倍数となるようなものの個数を解答してください．