OMC144(F)

　カタツムリ君が $n$ 回目に辺を伝って移動した時に $X$ からの距離が $1,2,3,4$ の頂点にいる場合の数をそれぞれ，$a_n, b_n, c_n, d_n$ とすると，求める場合の数は $d_{9999}$ である．また，以下の漸化式が成り立つ． $$a_{n+1}=b_{n}, \quad b_{n+1}=2a_{n}+b_{n}+c_{n}, \quad c_{n+1}=b_{n}+c_{n}+2d_{n}, \quad d_{n+1}=c_{n}$$ ここで，$s_n = a_n + d_n, t_n = a_n - d_n$ とすれば，$d_{9999} = \dfrac{s_{9999}- t_{9999}}{2}$ であるから，$s_{9999}$ と $t_{9999}$ を $5003$ で割った余りを求めればよい．以下では，合同式は全て $5003$ を法として考える．

• $s_{9999}$ を $5003$ で割った余り
  $$s_{1} = 3,\quad s_2 = 0,\quad s_{n} = b_{n-1} + c_{n-1} = 2(b_{n-2} + c_{n-2}) + 2(a_{n-2} + d_{n-2}) = 2s_{n-1} +2 s_{n-2}$$ である．ここで，奇素数 $p$ と整数 $a$ に対し $\bigg(\dfrac{a}{p}\bigg)$ をLegendre記号とすると，平方剰余の相互法則より $$\bigg(\dfrac{3}{5003}\bigg) = \bigg(\dfrac{5003}{3}\bigg)(-1)^{\frac{5003-1}{2}\cdot\frac{3-1}{2}} = 1$$ であるので，$r^2 \equiv 3$ なる整数 $r$ が存在する．このとき， $$s_n \equiv \frac{r}{2}\big((1+r)(1-r)^{n-1} - (1-r)(1+r)^{n-1}\big)$$ であることが確認できる．従って， $$\begin{aligned} s_{9999} &\equiv \frac{r}{2}\big((1+r)(1-r)^{9998} - (1-r)(1+r)^{9998}\big)\\ &\equiv \frac{r}{2}\bigg(\frac{1+r}{(1-r)^6} - \frac{1-r}{(1+r)^6}\bigg)\\ &= \frac{r\big((1+r)^7 - (1-r)^7\big)}{2(1-r^2)^6}\\ &= \frac{\sum\limits_{k=1}^{4}{}_{7}\mathrm{C}_{2k-1}r^{2k}}{(1-r^2)^6}\\ &\equiv \frac{\sum\limits_{k=1}^{4}{}_{7}\mathrm{C}_{2k-1}3^k}{(-2)^6}\\ &\equiv \frac{123}{8} \end{aligned}$$ である．もしくは，$s_{9999}\equiv s_{-5}$ であるから，漸化式を逆順に辿ることでも同様の結果を得られる．

• $t_{9999}$ を $5003$ で割った余り
  $$t_n = b_{n-1} - c_{n-1} = (2a_{n-2} + b_{n-2} + c_{n-2}) - (b_{n-2} + c_{n-2} + 2d_{n-2}) = 2(a_{n-2} - d_{n-2})$$ である．また，$a_1-d_1=3$ であるから， $$a_{9999}-d_{9999}=3\times 2^{4999}\equiv 3\times2^{-3}\equiv \frac38$$ である．

以上より，求める答えは $d_{9999}\equiv\dfrac12\biggl(\dfrac{123}{8}-\dfrac38\biggr) \equiv \dfrac{15}{2}\equiv \bf{2509}$ である．