問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 行 $N$ 列のマス目があり, 上から $i$ 行目, 左から $j$ 列目をマス $(i,j)$ と呼ぶことにする. マス $(i,j)$ には非負整数 $A_{i,j}$ が書かれている.

マス $(1,1)$ から右か下のマスに移動することを繰り返すことによってマス $(N,N)$ へ移動する方法のうち, 通ったマスに書かれている非負整数の排他的論理和が $0$ となるのは何通りか?

制約

$2 \leq N \leq 20$
$0 \leq A_{i,j} \lt 2^{30}$

解法

マス $(1,1)$ から右か下のマスに移動することを繰り返すことによってマス $(N,N)$ へ移動する方法とは, 右のマスへの移動 $(N-1)$ 回, 下のマスへの移動 $(N-1)$ 回の計 $(2N-2)$ 回である.

ここで, 前半 $(N-1)$ 回の移動について考える. このとき, 前半の $(N-1)$ 回の移動については右, 下の移動がそれぞれ $(N-1)$ 回だけなので回数の各移動の制限回数も発生せず, 全部で $2^{N-1}$ 通りである. ここで, $E[p, \beta]$ を次のように設定する.

前半 $(N-1)$ 回の移動のうち, 右へ移動したのが $p$ 回であり, (通ったマス $(1,1), (N-p,p+1)$ 共に含む) に書かれた整数の排他的論理和が $\beta$ であるような経路の数.

この $E[p, \beta]$ については前半の移動の場合の数が $2^{N-1}$ 通りであったから, 愚直な全探索を利用し, 辞書のリストで管理することによって求められる. 後半についても $F[p, \beta]$ を同様に

後半 $(N-1)$ 回の移動のうち, 右へ移動したのが $p$ 回であり, (通ったマス $(p+1, N-p)$ 共に含む) に書かれた整数の排他的論理和が $\beta$ であるような経路の数.

ここで, マス $(1,1)$ からマス $(N,N)$ への移動の方法で, マス $(N-p, p+1)$ を経由することと, 前半の移動で $p$ 回右に移動をすることが同値である. また, マス $(N-p, p+1)$ を経由するような $p$ は任意のマス $(1,1)$ からマス $(N,N)$ への移動の方法においてただ一つ存在する.