行列累乗で計算する方法をご紹介します。

\(1\) から \(k\) までの紙の色を決めたときに、青色に塗られた紙の魔数が \(2\mathbb{Z} + i\) 枚で、黄色に塗られた紙の枚数が \(2\mathbb{Z} + j\) であるような塗り方の数を \(\mathrm{dp}_k[i][j]\) とおくと、\(\mathrm{dp}_k\) から \(\mathrm{dp}_{k + 1}\) への遷移は、

• 紙 \(k + 1\) として赤色を選んだとき、\((i, j) → (i, j)\)
• 紙 \(k + 1\) として青色を選んだとき、\((i, j) → (i \oplus 1, j)\)
• 紙 \(k + 1\) として黄色を選んだとき、\((i, j) → (i, j \oplus 1)\)

（ただしここで \(\oplus\) は bitwise xor）となります。

したがって

\[ \begin{aligned} A &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ B &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ C &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \\ \end{aligned} \]

とおくと答えは

\[ \begin{aligned} \left(\mathrm{答え}\right) &= \left( {e_1}^T \otimes {e_2}^T \right) (A + B + C)^N \! \left(e_1 \otimes e_1 \right) \\ &= {e_3}^T\! \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix}^N\!\!\!\! e_1 \end{aligned} \]

で求められます。（解答終わり）

ちなみに真ん中の行列が Matrix of ones \(J\)、反対角成分に \(1\) が並んだ行列 \(K\) の差であることに気づくとさらにキレイになります。答えは \({e_3}^T (J - K)^N e_1\) と表せますが、\(JK = KJ\) に注意して展開すると各項 が

\[ {e_3}^T J^i (-K)^{N - i} e_1 = \begin{cases} 0 & i = 0 \\ 4^{i-1}(-1)^{N-i} & \mathrm{otherwise} \end{cases} \]

となるため、

\[ \begin{aligned} \left(\mathrm{答え}\right) = \frac14 \cdot \sum_{i = 1}^N 4^i(-1)^{N-i} = \frac{3^N - (-1)^N}{4} \end{aligned} \]

となり、公式解説の結果に一致することもわかります。