　$3×20$ のマス目を考え，上から $a_i$ 行目，左から $b_i$ 行目のマスを $X_i$ とする．このとき，$X_1,X_2,\ldots,X_{60}$ はマス目の全てのマスを通り，左上のマスから右上のマスまで，辺を共有したマスを辿る道になっているから，このような道の個数を数えれば良い．以下では，上から $c$ 行目，左から $d$ 行目のマスを $[c,d]$ で表す．\
　$[1,1]$ から $0$ 回以上右に進み，初めて下に進んだマスを $[2,k]$ とすると，道はそこから
$$[2,k]→ \cdots →[2,1]→[3,1]→ \cdots →[3,k]→[3,k+1]$$
と一意に定まることが分かる．特に，$3×n$ のマス目について，$[1,1]→[1,n]→[3,1]→[3,n]$ と通る道はちょうど $1$ つ存在する．従って，$3×20$ のマス目をいくつかの $3×n$ のマス目に分ける方法を考えれば，それと道が $1$ 対 $1$ 対応する．ただし，このままでは終点が $[1,20]$ ではなく $[3,20]$ ともなりうることに留意する．\
　上のマス目の分け方を次のように考える．

- $3×20$ のマス目を分けている縦の線 $19$ 本のうち，$0$ 本以上を選び，それを境界とする．

　このとき，境界を $1$ 本引くと終点の右上・右下が入れ替わるため，境界はちょうど奇数本引けば良い．$19$ 本目の境界を最後に選べば，その有無で偶奇を調整できるため，特に求める答は $2^{18}=\mathbf{262144}$ である．\
　以下に $3×7$ のマス目を $3$ 本の境界で分けた場合を示す：

![figure 1](\/images\/xNRJcAwsvaqfsepIfXOCMZGuq4D4NTFwfIqDFrcC)
公式解説
https://onlinemathcontest.com/contests/omc211/editorial/7007
3\/5中に執筆
漸化式による数え上げ
https://onlinemathcontest.com/contests/omc211/editorial/7007/435
　公式解説と同様の考察により, 求める答えは, $20$ を偶数個の正整数に分割する方法の数であるとわかる.
$$f=x+x^2+x^3+\cdots=\frac{x}{1-x}$$
とすると $20$ を $k$ 個の正整数に分割する方法は, 
$$\[x^{20}\](x+x^2+x^3+\cdots)^k=\[x^{20}\]f^k$$
であるから $k=0,2,4,8,\dots$ について, $\[x^{20}\]f^k$ を合計すれば求める答えは,
$$
\begin{aligned}
\sum_{n=0}^{\infty}\[x^{20}\]f^{2n}&=\[x^{20}\]\sum_{n=0}^{\infty}f^{2n}\\\\
&=\[x^{20}\]\frac{1}{1-f^2}\\\\
&=\[x^{20}\]\frac{1}{1-\Big(\dfrac{x}{1-x}\Big)^2}\\\\
&=\[x^{20}\]\frac{1-2x+x^2}{1-2x}\\\\
&=\[x^{20}\]\frac{1}{1-2x}-2\[x^{19}\]\frac{1}{1-2x}+\[x^{18}\]\frac{1}{1-2x}\\\\
&=2^{20}-2\times2^{19}+2^{18}\\\\
&=2^{18}
\end{aligned}
$$
ユーザー解説
https://onlinemathcontest.com/contests/omc211/editorial/7007/655
　$1$ 以上 $3$ 以下の整数の組 $(a_1,a_2,\ldots,a_{60})$ と $1$ 以上 $20$ 以下の整数の組
 $(b_1,b_2,\ldots,b_{60})$ のペアであって，以下の条件をすべてみたすものはいくつありますか．

- $a_1=a_{60}=b_1=1, ~ b_{60}=20$．
- $i=1,2,\ldots,59$ それぞれについて，以下の一方が成り立つ：
	- $|a_{i}-a_{i+1}|=1$ かつ $b_i=b_{i+1}$．
	- $a_i=a_{i+1}$ かつ $|b_{i}-b_{i+1}|=1$．
- 組 $(a_1,b_1),(a_2,b_2),\ldots,(a_{60},b_{60})$ は相異なる．