　格子点であって $x, y$ 座標がともに $3$ の倍数となるものを**白い点**と呼び，$x, y$ 座標をそれぞれ $3$ で割ったとき，一方が余り $1$ でもう一方が余り $2$ となるものを**黒い点**と呼ぶ．任意の $1 \leq n \leq 36$ なる整数 $n$ に対し $P_n$ の $x, y$ 座標の和は $n$ なので，OMC君の移動を繰り返す方法によらず $P_3, P_6, ..., P_{36}$ の $12$ 個は必ず白い点か黒い点である．逆に，$P_1, P_2, ..., P_{36}$ のうち先ほどの $12$ 個以外の $24$ 個は，必ず白い点でも黒い点でもない．$P_3, P_6, ..., P_{36}$ のうちちょうど $1$ 個が白い点となるような移動の繰り返しを数えればよい．また，$1$ 回の移動のうち $x, y$ 軸の正の方向に移動することを，それぞれ「右」「上」と表すことにする． \
　まずは白い点を起点とし移動を $3$ 回繰り返したとき，移動後に白い点・黒い点に到達する移動方法をそれぞれ数えよう．白い点に到達するのは「右に $3$ 回連続移動」または「上に $3$ 回連続移動」の $2$ 通りであり，黒い点に到達するのはそれ以外の $2^3 - 2 = 6$ 通りである． \
　次に黒い点を起点とし移動を $3$ 回繰り返したとき，移動後に白い点・黒い点に到達する移動方法をそれぞれ数えよう．到達し得る $4$ つの点のうち白い点はちょうど $1$ つであり，なおかつそれは「右に $1$，上に $2$ 移動した先」か「右に $2$，上に $1$ 移動した先」に位置する．どちらの場合にせよ白い点に到達するのは ${}\_{3}\mathrm{C}\_{1} = 3$ 通りであり，黒い点に到達するのは $2^3 - 3 = 5$ 通りである． \
　以後，$P_0$ は原点であるとする（$P_0$ は白い点である）．また，$P_0$ から $P_{36}$ までの移動の繰り返しを，「$P_0$ から $P_3$」「$P_3$ から $P_6$」・・・「$P_{33}$ から $P_{36}$」の  $12$ 回の移動に分割して考える．この $12$ 回に含まれる「白い点から白い点」「白い点から黒い点」「黒い点から白い点」「黒い点から黒い点」に移動する回数をそれぞれ $(W_w, W_b, B_w, B_b)$ と表す．$P_3, P_6, ..., P_{36}$ のうちどれが白い点かが決まっていれば，その条件のもとで移動を繰り返す方法の個数は
$$2^{W_w} \times 6^{W_b} \times 3^{B_w} \times 5^{B_b}$$

と表せる．$P_3, P_6, ..., P_{36}$ のうち白い点となるものの選び方すべてに対するこの値の総和を求めればよい． $(W_w, W_b, B_w, B_b)$ は以下の $3$ 通りがあり得る．
- 白い点が $P_3$ のとき，$(W_w, W_b, B_w, B_b) = (1, 1, 0, 10)$ である．
- 白い点が $P_{36}$ のとき，$(W_w, W_b, B_w, B_b) = (0, 1, 1, 10)$ である．
- 白い点が $P_6, P_9, ..., P_{33}$ のいずれかであるとき，$(W_w, W_b, B_w, B_b) = (0, 2, 1, 9)$ である．

特に $3$ 番目のケースだと白い点の候補が $10$ 個あることに注意すれば，求める個数は次のように計算できる．
$$2 \times 6 \times 5^{10} + 6 \times 3 \times 5^{10} + 6^2 \times 3 \times 5^9 \times 10 = \mathbf{2402343750}$$
公式解説
https://onlinemathcontest.com/contests/omce003/editorial/11150
　公式解説と同様に，$x,y$ 座標がともに $3$ の倍数であるような点を**白い点**と呼ぶ．\
　移動を $3k$ 回繰り返したときに，
- $P_1, \cdots, P_{3k}$ のうち白い点が存在しない場合の数を $a_k$
- $P_1, \cdots, P_{3k-1}$ はいずれも白い点でなく，$P_{3k}$ が白い点であるような場合の数を $b_k$
- $P_1, \cdots, P_{3k}$ のうちちょうど一つが白い点であり，それは $P_{3k}$ ではないような場合の数を $c_k$

とおく．これらは互いに排反であり，いま求めたいものは $b_{12}+c_{12}$ である．\
　公式解説と同様に，これらの場合の遷移を考えると，次の漸化式を得る：
$$\begin{aligned}
    a_{n+1} &= 5a_n \\\\
    b_{n+1} &= 3a_n \\\\
    c_{n+1} &= 6b_n+5c_n
    \end{aligned}$$
　あとは $a_1=6, b_1=2, c_1=0$ を用いて漸化式を解けばよい．$b_n=18×5^{n-2}\ \  (n≧2)$ は容易にわかるので，
$$c_{n+1}=5c_n+108×5^{n-2}, c_2=12$$
 を解けばよいことがわかる．これを解けば $c_n=(108n-156)×5^{n-3}\ \ (n≧2)$ となり，求めるべき値は
$$b_{12}+c_{12}=18×5^{10}+1140×5^9=246×5^{10}=\mathbf{2402343750}$$
漸化式を作って解く
https://onlinemathcontest.com/contests/omce003/editorial/11150/500
結論から言うと答えはこの値になります

$$\begin{pmatrix}0&1&0&2\\\\\end{pmatrix}\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^{12}\begin{pmatrix}1\\\\0\\\\0\\\\0\\\\\end{pmatrix}$$

# 証明

$P_{3n}$の時点にて、
- $(x_{3n}\mod{3},y_{3n}\mod{3})=(0,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるものを$a_n$
- $(x_{3n}\mod{3},y_{3n}\mod{3})=(0,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるものを$b_n$
- $(x_{3n}\mod{3},y_{3n}\mod{3})= (1,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるものを$c_n$
- $(x_{3n}\mod{3},y_{3n}\mod{3})= (1,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるものを$d_n$

とする。$(a_0,b_0,c_0,d_0)=(1,0,0,0)$である。

このとき、
- $(x_{3n}\mod{3},y_{3n}\mod{3})= (2,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=c_n$
- $(x_{3n}\mod{3},y_{3n}\mod{3})= (2,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=d_n$

が成り立つ。


このとき、

- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (0,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=a_n+c_n$
- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (1,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=a_n+c_n$
- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (2,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=2c_n$
- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (0,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=b_n+d_n$
- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (1,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=b_n+d_n$
- $(x_{3n+1}\mod{3},y_{3n+1}\mod{3})= (2,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=2d_n$

であり、

- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (0,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=a_n+3c_n$
- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (0,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=b_n+3d_n$
- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (2,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=a_n+3c_n$
- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (2,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=b_n+3d_n$
- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (1,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=2a_n+2c_n$
- $(x_{3n+2}\mod{3},y_{3n+2}\mod{3})= (1,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=2b_n+2d_n$

であり、

- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (0,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=2a_n+6c_n=b_{n+1}$
- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (0,0)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が2回であるもの$=2b_n+6d_n$
- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (1,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=3a_n+5c_n=c_{n+1}$
- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (1,2)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=3b_n+5d_n=d_{n+1}$
- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (2,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が0回であるもの$=3a_n+5c_n=c_{n+1}$
- $(x_{3n+3}\mod{3},y_{3n+3}\mod{3})= (2,1)$かつ$(x\mod{3},y\mod{3})=(0,0)$なる点を通った回数が1回であるもの$=3b_n+5d_n=d_{n+1}$



となる。よって、

$$\begin{pmatrix}a_n\\\\b_n\\\\c_n\\\\d_n\\\\\end{pmatrix}=\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^{n}\begin{pmatrix}1\\\\0\\\\0\\\\0\\\\\end{pmatrix}$$

である。求めるべき答えは$b_{12}+2d_{12}$なので左から$\begin{pmatrix}0&1&0&2\\\\\end{pmatrix}$を掛ければOKです

# 計算するテクニック

行列の$1,2,3,6,12$乗を計算すればOKです。

$$\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^2=\begin{pmatrix}0&0&0&0\\\\18&0&30&0\\\\15&0&25&0\\\\6&15&18&25\end{pmatrix}$$

$$\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^3=\begin{pmatrix}0&0&0&0\\\\18&0&30&0\\\\15&0&25&0\\\\6&15&18&25\end{pmatrix}\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}=\begin{pmatrix}0&0&0&0\\\\90&0&150&0\\\\75&0&125&0\\\\84&75&180&125\end{pmatrix}$$

$$\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^6=\begin{pmatrix}0&0&0&0\\\\90&0&150&0\\\\75&0&125&0\\\\84&75&180&125\end{pmatrix}^2=125 \begin{pmatrix}0&0&0&0\\\\90&0&150&0\\\\75&0&125&0\\\\246&75&450&125\end{pmatrix}$$

ここで、
$$\begin{pmatrix}0&0&0&0\\\\2&0&6&0\\\\3&0&5&0\\\\0&3&0&5\end{pmatrix}^{12}$$

については、1行目2列目の成分と1行目4列目の成分だけ計算できればよい。

よって、

$$125^2\left(150\cdot 75+2\cdot (75\cdot 90+75\cdot 450+246\cdot 125)\right)=\bm{2402343750}$$
体育会系数学
https://onlinemathcontest.com/contests/omce003/editorial/11150/515
　はじめ，OMC君は $xy$ 平面の原点におり，以下どちらかの移動を合計 $36$ 回繰り返します．
- $x$ 軸の正の方向に $1$ 移動する．
- $y$ 軸の正の方向に $1$ 移動する．

ここで $1 \leq n \leq 36$ なる整数 $n$ に対し，移動を $n$ 回繰り返した時点でOMC君がいる点を $P_n$ と表します．OMC君が移動を繰り返す方法は全部で $2^{36}$ 通りありますが，そのうち次の条件をみたすものは全部でいくつありますか？
- $P_1, P_2, ..., P_{36}$ のうちちょうど $1$ つは，$x, y$ 座標がともに $3$ の倍数である．