　以下の $2$ 種類の操作を考える：

- $(P_i)$ $:i$ 行目の白いマスのうち隣接する $2$ マスの組を互いに交わらないようにいくつか選び，それらを黒く塗る．
- $(Q_i)$ $:i$ 行目の白いマスおよびその下に隣接するマスを全て黒く塗る．

　このとき，白いマス全体を $1\times 2$ の長方形で敷き詰められることは，$(P_1)\to (Q_1)\to (P_2)\to (Q_2)\to \cdots\to (P_5)$ という操作により全てのマスを黒にできることと同値である．\
　白を $0$ に，黒を $1$ に対応させることで，各行の状態を長さ $20$ のビット列で表すことができる．これを行の**コード**と呼ぶことにする．
$(P_i)$ を行った直後の $i$ 行目のコードを $a_i$ とし，$(Q_i)$ を行った直後の $i+1$ 行目のコードを $b_i$ とすると，これらは以下を満たす．ただし $b_0$ は初期状態の $1$ 行目のコードとする．

- $a_i$ は $b_{i-1}$ に対して，$00$ となっている部分を互いに交わらないように $0$ 個以上選び，それらを $11$ に置き換えることで得られる．
- $b_i$ は $a_i$ をビット反転したものである．

最終的に全てのマスが黒になることは，$a_5=11\cdots11$ となることと同値である．すなわち，この問題は以下の問題と等価である：

***
　長さ $20$ のビット列 $S$ であって，以下の $2$ 種類の操作を $(A)\to (B)\to (A)\to (B)\to (A)$ の順に行うことで $11\cdots 11$ にできるようなものはいくつあるか？

- $(A)$ $:00$ となっている部分を互いに交わらないように $0$ 個以上選び，それらを $11$ に置き換える．
- $(B)$ $:11$ となっている部分を互いに交わらないように $0$ 個以上選び，それらを $00$ に置き換える．
***

　ここで次の操作を考える．

- $(C)$ $:00$ または $11$ となっている部分を互いに交わらないように $0$ 個以上選び，それらをビット反転する．

すると， $S$ を操作 $(A)\to (B)\to (A)\to (B)\to (A)$ によって $11\cdots 11$ にできることは，$(C)\to (C)\to (C)\to (C)\to (C)$ によって $11\cdots 11$ にできることと同値である．


<details>
<summary>**同値であることの証明**<\/summary>
　$S$ を $(A)\to (B)\to (A)\to (B)\to (A)$ によって $11\cdots 11$ にできるならば，その操作をそのまま $(C)\to (C)\to (C)\to (C)\to (C)$ とみなすことができる．逆に $S$ を $(C)\to (C)\to (C)\to (C)\to (C)$ によって $11\cdots 11$ にできるならば，それぞれの $(C)$ を $(A)\to (B),(B)\to (A),\dots$ と分解することで $(A)\to (B)\to (A)\to (B)\to (A)\to (B)$ に置き換えることができる．最終的に $11\cdots 11$ になることから最後の $(B)$ は省略できる．
<\/details>

　$S$ の奇数番目のビットを反転したものを $T$ とすると，$(C)$ は $T$ に対する以下の操作に対応する：

- $(D)$ $:01$ または $10$ となっている部分を互いに交わらないように $0$ 個以上選び，それらをビット反転する．

よって，$(D)$ を $5$ 回行うことで $0101\cdots 01$ にできるような長さ $20$ のビット列 $T$ の個数を求めればよい．$T$ に含まれる $1$ の個数は $(D)$ の前後で不変なので $10$ 個である．$0,1$ をそれぞれ $x$ 方向，$y$ 方向への距離 $1$ の移動と対応させることで，$T$ は 平面上の点 $(0,0)$ から $(10,10)$ へ隣り合う格子点を通って行く最短経路と対応する．この経路上の $x-y$ の値の最大値 $M$ および最小値 $m$ は $(D)$ によって高々 $1$ しか変化しないため，$M \leq 6$ および $m\geq -5$ が必要である．逆に $T$ がこれらの条件をみたすならば，$5$ 回の操作で $(M,m)=(1,0)$（つまり $T=0101\cdots 01$）となるようにできるため，$T$ は条件を満たすビット列であることがわかる．

　以上よりこの問題の答えは，平面上の点 $(0,0)$ から $(10,10)$ へ隣り合う格子点を通って行く最短経路のうち，経路上で常に $-5\leq x-y\leq 6$ が成り立つものの個数に等しい．そこでこの条件を**満たさない**最短経路を数える．

- 経路上で $x-y\lt -5$ となる最短経路は，直線 $\ell \colon x-y=-6$ と初めて交わった点から先を $\ell$ で折り返すことにより，$(0,0)$ から $(4,16)$ への最短経路と一対一に対応する．
- 経路上で $x-y\gt 6$ となる最短経路は，直線 $m \colon x-y=7$ と初めて交わった点から先を $m$ で折り返すことにより，$(0,0)$ から $(17,3)$ への最短経路と一対一に対応する．

これらは同時に起こり得ないので，答えは
$$
\binom{20}{10}-\binom{20}{4}-\binom{20}{3}=\binom{20}{10}-\binom{21}{4}=\mathbf{178771}.
$$
公式解説
https://onlinemathcontest.com/contests/omce010/editorial/10982
　$5$ 行 $20$ 列の長方形のマス目があり，最初全てのマスが白く塗られています．$1$ 行目のマスのうち $0$ 個以上を黒く塗る方法は $2^{20}$ 通りありますが，そのうち以下の条件を満たすものはいくつありますか．

- $1\times 2$ の長方形によって，白いマス全体を重なりや隙間，はみ出しなく敷き詰めることができる．

ただし，$1\times 2$ の長方形は回転させてもよいとします．