OMC212(C)

　$2\times n$ のマス目の各マスを白と黒で塗る方法であって，左上のマスを黒で塗り，さらに問題の条件の「右下のマス」を「右端の $2$ マスのいずれか」に変えた条件をみたす方法の数を考える．このような方法のうち，$n$ 列目を上から順に黒と黒で塗る方法の数を $a_n$，黒と白で塗る方法の数を $b_n$，白と黒で塗る方法の数を $c_n$ とする（白と白で塗る場合は黒のマスのみをたどって右端に到達できないため，考えなくてよい）．このとき，$a_n , b_n , c_n$ の間に次の漸化式が成り立つ． $$a_{n+1} = b_n + c_n,\quad b_{n+1} = a_n + b_n,\quad c_{n+1} = a_n + c_n,\quad a_1 = 1, \quad b_1 = 1 , \quad c_1 = 0$$ これより， $$a_n + b_n + c_n=2(a_{n-1}+b_{n-1}+c_{n-1})=\cdots=2^{n-1}(a_1+b_1+c_1)=2^n,$$ $$b_n-c_n=b_{n-1}-c_{n-1}=\cdots=b_1-c_1=1$$ が分かる．また， $$b_{n+1} + c_{n+1} = 2(a_n + b_n + c_n) - (b_n + c_n) = 2^{n+1} - (b_n + c_n)$$ より，$b_1+c_1=1$ と併せて $$b_n + c_n = \cfrac{(-1)^n + 2^{n+1}}{3}$$ が従う．よって， $$c_n = \frac{(b_n + c_n) - (b_n - c_n)}{2} = \cfrac{(-1)^n + 2^{n+1} -3}{6}$$ と分かる．
　以上より，問いの条件を満たす塗り方の数は $a_{2024} + c_{2024} = c_{2025} = \cfrac{2^{2026}-4}{6}$ である．左上のマスが白色の場合も同様に考えることで，結局条件を満たす塗り方は $\cfrac{2^{2026}-4}{3}$ 通りと分かる．よって，フェルマーの小定理を用いることで，解答すべき値は $\mathbf{340}$ と分かる.