考察
各bitについて頂点値vector xを考えると、全頂点で隣接値XORが0という条件はGF(2)上の隣接行列Aに対するAx=0である。
各頂点へ非零整数を置くには、選んだkernel vector群のbitwise ORが全座標を覆えばよい。kernel基底で覆えない座標はkernelのどのvectorでも1にできない。
採用する候補: 隣接行列をGF(2)で掃き出してkernel基底を求め、基底indexを出力整数のbitへ割り当てる。
各bit vectorが条件式を満たし、基底のORによる座標被覆が非零条件の必要十分判定になる。
棄却する候補: 各頂点へ非零整数を順に割り当て、隣接XOR条件を後から局所修正する。
一頂点の変更が全隣接式へ同時に影響し、局所選択では連立一次制約を保てない。
kernelはXORで閉じるvector spaceなので、基底に現れない座標は全解で0、どれかの基底に現れる座標は対応bitで非零化できる。
N≤60なら各rowとvectorを64 bit maskにし、pivot消去でrank・free変数・kernel基底を構成できる。
隣接行列の各rowをbit maskにしてGF(2) Gaussian eliminationを行う。各free変数を1としたkernel基底vectorを復元し、そのORが全N bitを覆わなければNo。覆うなら基底b_kごとに、b_kの頂点i成分が1ならanswer_iのk bitを立て、Yesと全answerを出力する。
典型の発動条件
GF(2) nullspace構成
発動条件: XORによる線形条件を同時に満たすassignmentが必要なとき。
係数行列をbitset掃き出しし、free変数からkernel基底を得る。
基底vectorのbit packing
発動条件: 複数の0/1解を各要素の非零性を満たす整数へまとめたいとき。
解vectorごとに別の出力bitを割り当て、各座標の列を整数化する。
問題固有の要素
頂点値を直接未知数にせず、整数の各bitを独立なkernel解と見れば、XOR条件と非零条件を分離できる。
別の問題へ持ち帰る視点: bitwise制約ではbit planeごとの線形解を作り、最後に列方向へpackingする。
正当性
各bitの隣接XOR条件はAx=0であり、全合法bit列はkernel。どのkernel基底でもcoordinate iが全基底で0なら全kernelで0となり頂点iへ非零を置けない。逆に各coordinateがある基底で1なら基底番号を異なるbitとして重ねれば全頂点非零で、各bitがkernelなので全隣接XORも0。OR被覆条件は必要十分。
実装上の注意
- 自己loopなしでも行列対角を勝手に立てない。N=60のmask shiftと出力上限2^N未満をunsigned 64 bitで安全に扱う。
復習の核
- 得た各basisについてAx=0を再計算し、全answer_iが非零かassertする。free変数からpivot変数を復元する向きを固定する。
計算量と制約
時間
O(N³/w+N²)、w=64。bitmask消去とkernel基底復元。
空間
O(N²/w+N²)。出力値もN個。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 60; 0 \leq M \leq N(N-1)/2; 1 \leq u_i < v_i \leq N; (u_i, v_i) \neq (u_j, v_j) for i \neq j.; All input values are integers.
出典