　少なくとも $1$ 回ジャンプしたバッタは，三角形 $A_0B_0C_0$ の内部（周を含まない）に存在し，かつ重心上に存在しない（重心上に存在するならば，重心へジャンプする直前に $A_1, A_2, B_1, B_2, C_1, C_2$ のいずれかに存在する必要があるが，これは生じない）．\
　三角形 $A_0B_0C_0$ の各部分を図のように $P, Q, R, S, T$ とし（太破線 $P$，太実線 $Q$ は白丸を含まず，領域 $R, S, T$ は境界を含まない），$n$ 回のジャンプのあとバッタがそれぞれに存在する確率を $p_n, q_n, r_n, s_n, t_n\ (n=1, 2, \cdots)$ とおくと，以下の漸化式が成り立つ．
$$p_1=\dfrac{1}{3},\quad q_1=\dfrac{2}{3},\quad p_{n+1}=\dfrac{2}{9}p_n+\dfrac{1}{9}q_n,\quad q_{n+1}=\dfrac{4}{9}p_n+\dfrac{2}{9}q_n$$
$$s_1=t_1=0,\quad s_{n+1}=\dfrac{2}{9}p_n+\dfrac{2}{9}q_n+\dfrac{2}{9}r_n+\dfrac{4}{9}s_n+\dfrac{2}{3}t_n,\quad t_{n+1}=\dfrac{1}{9}p_n+\dfrac{1}{9}q_n+\dfrac{1}{9}r_n+\dfrac{2}{9}s_n+\dfrac{1}{3}t_n$$
よって，$q_n=2p_n$ であるから $p_{n+1}=\dfrac{4}{9}p_n$ が成り立ち，
$$p_n=\dfrac{2^{2(n-1)}}{3^{2n-1}}$$
を得る．また，$p_n+q_n+r_n=1-(s_n+t_n),\ s_n=2t_n$ であるから $t_{n+1}=\dfrac{4}{9}t_n+\dfrac{1}{9}$ が成り立ち，
$$t_n=\dfrac{3^{2(n-1)}-2^{2(n-1)}}{5\times3^{2(n-1)}}$$
を得る．求める確率は $1-(p_8+t_8)=\dfrac{4\times3^{15}-2^{15}}{5\times3^{15}}$ （この分母と分子は $5$ で割り切れることに注意）であるから，特に解答すべき値は $\bf{25821479}$．

![figure 1](\/images\/IkqMuNAU7DxskdxutxRnyMxKM7bcbhkKleUSjwBd)
公式解説
https://onlinemathcontest.com/contests/omc218/editorial/6204
　バッタではなく，動点 $K$ が条件を満たしながら移動するものと考える（以下「高さ」という表現を用いるため，バッタのままだと，バッタが空中に浮いているような変な状況が想像されうる）．

　直線 $B_0C_0$ が高さ $0$ に存在し（$x$ 軸上にあると想像すればよい），点 $A_0$ が高さ $3$ に存在すると考えよう．\
　はじめ点 $K$ が存在する場所は高さ $1$ であり，$\triangle A_0 A_1 C_2$ は高さ $2$ と $3$ の間に存在する．\
　 $P_n(\ast)$ で，$n$ 回の移動後に動点 $K$ の高さ $h$ が条件 $\ast$ を満たす確率，を表すことにする．たとえば $P_0(h=1)=1$，$P_0(0 \lt h \lt 1)=0$ である．\
　$8$ 回目の移動後に動点 $K$ が $\triangle A_0 A_1 C_2$ の周上または内部に存在する確率は $P_8(2 \leq h \lt 3)$ である．対称性を考えれば，いま求めたい確率は，$1-3×P_8(2 \leq h \lt 3)$ である．

---

　計算のしやすさのために，改めて次のように置き直す．
$$x_n=P_n(2 \leq h \lt 3), y_n=P_n(1 \leq h \lt 2), z_n=P_n(0 \lt h \lt 1)$$
　これから $x_n, y_n, z_n$ に関する漸化式を立てて，$x_6$ を求めたい．そこで実際に漸化式を立てると，
$$\begin{aligned}
x_{n+1} &=\dfrac{3x_n+y_n}{9}\\\\
y_{n+1} &=\dfrac{6x_n+4y_n+3z_n}{9}\\\\
z_{n+1} &=\dfrac{4y_n+6z_n}{9}
\end{aligned}$$
　$x_n+y_n+z_n=1$ を $z_n$ について解いて，第二式に代入すると，次の式を得る．
$$y_{n+1} =\dfrac{3x_n+y_n}{9}+\dfrac{1}{3}$$
　すなわち，$n \geq 1$ の範囲で，$y_n=x_n+\dfrac{1}{3}$ である．これを用いれば $x_{n+1} =\dfrac{3x_n+y_n}{9}$ は次のように変形される．
$$x_{n+1}=\dfrac{4}{9}x_n+\dfrac{1}{27}$$
　$x_1=\dfrac{1}{9}$ を用いて漸化式を解けば，$x_n=\dfrac{2}{45}\left(\dfrac{4}{9}\right)^{n-1}+\dfrac{1}{15}$ となり，$x_8=\dfrac{2^{15}+3^{15}}{5×3^{16}}$，求めるべき値は $1-3x_6=\dfrac{4×3^{15}-2^{15}}{5×3^{15}}$ である．
3変数の漸化式で解く方法
https://onlinemathcontest.com/contests/omc218/editorial/6204/469
　$A_0,B_0,C_0$ の位置ベクトルを ,$a,b,c$ とし, $xa+yb+zc\quad (x+y+z=1)$ で表される点を$ (x,y,z)$ と表現することにします.\
　バッタは最初 $(1\/3,1\/3,1\/3)$ にいて, ジャンプによって, 以下のいずれかと平均を取ります.
$$
\begin{aligned}(1,0,0),(0,1,0),(0,0,1),\\\\
\Big(\frac{1}{3},\frac{2}{3},0\Big),\Big(0,\frac{1}{3},\frac{2}{3}\Big)\Big(\frac{2}{3},0,\frac{1}{3}\Big),\\\\
\Big(\frac{2}{3},\frac{1}{3},0\Big),\Big(0,\frac{2}{3},\frac{1}{3}\Big)\Big(\frac{1}{3},0,\frac{2}{3}\Big)\\\\
\end{aligned}$$
 $i$番目のジャンプで選んだ点を $(x_i,y_i,z_i)$ とすると, $8$ 回目のジャンプの後バッタの位置は, 以下になります.
$$\Big(\frac{1}{2^8}\frac{1}{3}+\sum_{i=1}^8\frac{1}{2^{9-i}}x_i,\frac{1}{2^8}\frac{1}{3}+\sum_{i=1}^8\frac{1}{2^{9-i}}y_i, \frac{1}{2^8}\frac{1}{3}+\sum_{i=1}^8\frac{1}{2^{9-i}}z_i\Big)$$
　点 $(x,y,z)$ が六角形内に含まれる条件は, $x\lt2\/3,y\lt2\/3,z\lt2\/3$ であるので, 条件は以下と同値です.
<details> <summary> 証明 <\/summary> 
　直線 $A_1C_2$ に関して, $A_0$ と同じ側にある条件を考える. $A_1,C_2$ はそれぞれ, $(2\/3,1\/3,0),(2\/3,0,1\/3)$ であるので, $A_1C_2$ 上にある点は, 
$$(x,y,z)=t\Big(\frac{2}{3},\frac{1}{3},0\Big)+(1-t)\Big(\frac{2}{3},0,\frac{1}{3}\Big)=\Big(\frac{2}{3},\frac{1}{3}t,\frac{1}{3}(1-t)\Big)$$
と表され, $(x,y,z)$ が $A_1C_2$ 上にある必要十分条件は $x=2\/3$ であり, $A_0$ については, $x=1\gt 2\/3$ であるので, 直線 $A_1C_2$ に関して, $A_0$ と同じ側にある条件は$x\gt 2\/3$.$x\lt2\/3,y\lt2\/3,z\lt2\/3$ であるとき, 六角形の外側の小さい三角形には含まれないのでこれが条件である. (バッタは常に三角形 $A_0B_0C_0$内にあることに注意.)<\/details>
$$
\begin{aligned}(3x_1)+2(3x_2)+4(3x_3)+\dots+128(3x_8)\lt 2^9-1,\\\\
(3y_1)+2(3y_2)+4(3y_3)+\dots+128(3y_8)\lt 2^9-1,\\\\
(3z_1)+2(3z_2)+4(3z_3)+\dots+128(3z_8)\lt 2^9-1\\\\
\end{aligned}$$
　集合 $U$ を以下で,定めると, $(3x_i,3y_i,3z_i)\in U$ であるので,
$$
\begin{aligned}U=&\\{(3,0,0),(0,3,0),(0,0,3),\\\\
&(1,2,0),(0,1,2),(2,0,1),\\\\
&(2,1,0),(0,2,1),(1,0,2)\\}
\end{aligned}
$$
$x,y,z$ の多項式 $P(x,y,z)$ を
$$P(x,y,z)=x^3+y^3+z^3+xy^2+yz^2+zx^2+x^2y+y^2z+z^2x$$ 
とすると, バッタが六角形内に含まれる場合の数は, 
$$P(x,y,z)P(x^2,y^2,z^2)P(x^4,y^4,z^4)\cdots P(x^{128},y^{128},z^{128})$$
 を展開したときの, $x,y,z$ それぞれの次数が $2^9-1$ より小さいもの係数の総和である. また 
$$P(x,y,z)=(x+y+z)(x^2+y^2+z^2)$$
 であるので, $Q(x,y,z)=x+y+z$ とおくと, 
$$
\begin{aligned}
&P(x,y,z)P(x^2,y^2,z^2)P(x^4,y^4,z^4)\cdots P(x^{128},y^{128},z^{128})\\\\
=&Q(x,y,z)\times(Q(x^2,y^2,z^2))^2(Q(x^4,y^4,z^4))^2\cdots(Q(x^{128},y^{128},z^{128}))^2\times Q(x^{256},y^{256},z^{256})
\end{aligned}$$
となる. よって, 以下の問題を解けば良い.

---
**問題**.
　$3$ つの数 $x,y,z$ があり, 初め $x=y=z=0$ です. $i=1,2,\dots,9$ について, $i$ 回目のターンに以下の操作を行います.
- $x,y,z$ の中から一つ選ぶ.
- 選んだ数に $2^{9-i}$ を足す.
- $i=2,3,\dots,8$ のとき, もう一度これを繰り返す.

　このとき, $x,y,z$ のどれも $2^9-1$ より, 小さくなるような操作列は何通りありますか？

---
　一番最初に $2^8$ を選んだ数を $x$ とします. 結論を述べると $x$ を一度も選ばないターンが存在し, 初めて $x$ を一度も選ばないターンまで, $x$を $2$ 度選ばないことが必要十分条件となります.
<details> <summary> 証明 <\/summary>
　以下より従う.

- $y,z$ はどのように貪欲に操作を行っても $2(2^7+2^6+\dots+2)+1=2^9-3$ 以下になる.

- 最後まで $x$ を一度以上選び続けると $x\geq 2^8+2^7+\dots+1=2^9-1$ となってしまう.

- $i (\geq 2)$ について, $i-1$ ターン目までに $x$ を $1$ 度ずつ選び, $i$ ターン目に $x$ を $2$ 回選んでしまった場合. $x\geq 2^8+\dots 2^{9-(i-1)} +2\times 2^{9-i}=2^9$ となる.

- $i (\geq 2)$ について, 逆に $i$ ターン目に $x$ を一度も選ばず, $i-1$ ターン目まで $x$ を一回ずつ選んだとすると, $i+1$ ターン以降貪欲に $x$ を最大化しても, $x\leq 2^8+\dots +2^{9-i}+2(2^{9-(i+1)}+\dots 2)+1=2^9-3$ となる.<\/details>


　よって, $i=2,\dots,9$ ターン目に $x$ を一度も選ばず, それまでに $x$ を一度ずつ選ぶ方法を足しあげれば良い.
- $i=2,\dots,8$ のとき, $x$ を $2$ から $i-1$ までの各ターンについて $x$ を一度ずつ選ぶ方法は ,$x\leftaroow y,z$ か $y,z\leftarrow x$ の $4$ 通り, $i$ ターン目に $x$ を一度も選ばない方法は $y,z \leftarrow y,z$ の $4$ 通り. 後は, $i+1$ から $8$ ターン目まで $9$ 通り. $9$ ターン目は $3$ 通り. よって, $4^{i-1}\times 9^{8-i}\times 3$ 通り.
- $i=9$ のとき, $x$ を $2$ から $i-1$ までの各ターンについて $x$ を一度ずつ選ぶ方法は $4$ 通り. $9$ ターン目に $1$ 度も $x$ を選ばない方法は $2$ 通り. よって, $4^7\times 2$通り.
　
　これより, 条件を満たす操作列は, (最初に $y,z$ を選んだとしても同様であるから)
$$3\times\Big(4^7\times 2+\sum_{i=2}^{8}4^{i-1}\times 9^{8-i}\times 3\Big)=\mathbf{34417716}$$
通りある.
ユーザー解説
https://onlinemathcontest.com/contests/omc218/editorial/6204/609
　三角形 $A_0B_0C_0$ において各辺を $3$ 等分し，辺 $A_0B_0$ 上の分点を $A_0$ に近い方から順に $A_1, A_2$，辺 $B_0C_0$ 上の分点を $B_0$ に近い方から順に $B_1, B_2$，辺 $C_0A_0$ 上の分点を $C_0$ に近い方から順に $C_1, C_2$ とおきます．はじめ，三角形 $A_0B_0C_0$ の重心にバッタがいます．このバッタが，$A_0, A_1, A_2, B_0, B_1, B_2, C_0, C_1, C_2$ から無作為に $1$ 点を選び，そのときバッタがいる地点と選んだ点の中点へジャンプすることを $8$ 回繰り返します．ちょうど $8$ 回のジャンプのあとバッタが六角形 $A_1A_2B_1B_2C_1C_2$ の内部（周を含まない）に存在する確率を求めてください．ただし，求める確率は互いに素な正整数 $a, b$ を用いて $\dfrac{a}{b}$ と表されるので，$a+b$ を解答してください．