京セラプログラミングコンテスト2022 (AtCoder Beginner Contest 271) F - XOR on Grid Path (500)
移動経路は$ _{2n-2}C_{n-1}通りあり全探索するには多すぎる
$ i+j=n+1となるマスのスタート地点側とゴール地点側に分けて考える
$ (1,1),(N,N)から上の分けた地点へ到達することを考える
この時分けた地点での取り得る値とその場合の数を記録しておく
これは簡単にDFSでできる
取り得る値は$ \mathcal{O}(2^N)になるので配列ではなくMapなどで持つ
ある地点についてスタートとゴールからの取り得る値がそのマスの値と同じになれば全体でXORが0になるということなのでこの数を合計する
最後の処理がボトルネックで$ \mathcal{O}(N2^N)