考察
任意のmonotone pathはx+y=N+1のanti-diagonal上のちょうど一つのcellを通り、そこまでにN−1 moves、そこからN−1 movesへ二分できる。
全path数は最大約3.5×10^10だが、各half pathの総数は片側2^(N−1)なのでN≤20なら列挙できる。
棄却する候補: startからgoalへの全monotone pathsを列挙してvisited valuesのXORを計算する。
中央二項係数C(38,19)規模となり列挙不能である。
採用する候補: start側とgoal側からanti-diagonalまでhalf pathsを列挙し、meeting cell別のXOR frequencyを照合する。
典型の発動条件
grid pathの半分全列挙
発動条件: path lengthは小さいが全path数が大きく、全pathが中央layerで一意に二分できるとき。
両端からN−1 movesだけDFSし、anti-diagonal cellごとにhalf-path情報を集める。
XOR頻度のmeet-in-the-middle
発動条件: 全体のXOR条件を左右partial XOR間の一意なmatching valueへ変形できるとき。
一方のXOR frequencyをmapにし、他方の各qに必要なpのcountを加える。
問題固有の要素
meeting cellは両halfで二重にXORされるため、結合条件でa_{x,y}を一度追加してfull pathでは一度だけ含まれるよう補正する。
別の問題へ持ち帰る視点: meet-in-the-middleでは境界要素が左右のどちらに含まれるかを式で固定し、重複・欠落を補正する。
正当性
両half XORがmeeting valueをともに含むなら、full XOR=0は p⊕a_{x,y}⊕q=0、すなわちq=p⊕a_{x,y}と同値である。 XOR valueは同じものが複数pathから生じるため、setではなくfrequency mapを使い、matching frequenciesの積を答えへ足す。 各full pathが一意なhalf-path pairに対応し、総列挙量を指数の半分へ落とせる。
実装上の注意
- forward/backward DFSをちょうどN−1 movesで止め、meeting cell座標をkeyの一部として混在を防ぐ。
- 答えはpath数で32 bitを超えるため64 bit整数を使い、meeting valueの包含規約を両DFSで統一する。
復習の核
- 組合せpath数が大きい一方でlengthが40程度なら、全pathが一度だけ通る中央layerで二分する。
- 左右情報を照合する前に、meeting elementを含む回数をXOR式として明示する。
計算量と制約
時間
O(N2ᴺ)の保守的上界、半path列挙とmap照合の対数因子を含む。
空間
O(2ᴺ)、meeting cell別XOR頻度。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 20; 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N); All values in the input are integers.
出典