NF杯2024(Q) - 2つの母関数(多項式)を用いる解法

　$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.$$