OMC182(C)

　全体を，頂点が正 $3n$ 角形の頂点，辺（有向）が各頂点とその頂点から操作を一回行った時のコインの行き先の頂点を結ぶ有向グラフとみなす．このグラフが閉路を持つのは明らかであり，その閉路の大きさの最小値は $n$ であるから，条件を満たす頂点はこのときの閉路上のすべての頂点のみである．
　従って，条件を満たす頂点は $\bmod\ 3$ で等しい頂点 $n$ 個の組でなければならず，これらの頂点にはすべて $3$ が書き込まれていることがわかる．
　ここで上記のように頂点 $n$ 個の組からなる閉路を持ち，かつ，他にも閉路を持つとき，その閉路は頂点をちょうど $n$ 個持つ． 　

　ここで，長さ $n$ の閉路をちょうど二つ持つ書き込み方は $3\times2^{n}-3$ 通り，ちょうど三つ持つような書き込み方は $1$ 通りであるから $$\begin{aligned} a_n &=3 \times 2^{2n}-2 \times (3 \times 2^{n}-3)-3 \times 1 \\ &=3 \times 4^{n}-6 \times 2^{n}+3 \end{aligned}$$ である．あるいは，長さ $n$ の閉路の選び方 $3$ 通りに，閉路を $1$ つずつずらした $n$ 頂点の決め方 $(2^n-1)^2$ を乗じることでも同じ表式を得る．
　よって求めるべき値は $$\begin{aligned} \sum_{n=1}^{2023}a_n &=\sum_{n=1}^{2023}(3 \times 4^{n}-6 \times 2^{n}+3) \\ & \equiv 3 \times \sum_{n=1}^{7}4^{n}-6 \times \sum_{n=1}^{14}2^{n}+3 \times 2023\\ &=3 \times \frac{4^{8}-4}{3}-6 \times (2^{15}-2)+3 \times 2023 \\ & \equiv -4+12+6069\\ &=\mathbf{6077} \pmod{2^{16}} \end{aligned}$$ である．