\(1\) 以上 \(2^N\) 未満の整数を書き込んで条件を満たす方法を説明します．

条件の整理

まず，問題文の条件を，行列とベクトルを用いて表します．以下の説明では，足し算と掛け算はすべて \(\mathrm{mod}\,2\) で考えることとします．XOR は \(\mathrm{mod}\,2\) の足し算にほかなりません．

与えられたグラフの隣接行列を \(A\) とします．すなわち，\(A\) は \(N \times N\) の行列で，頂点 \(i,j\) の間に辺があるときは \(A_{ij}=1\)，そうでないときは \(A_{ij}=0\) とします．

また，頂点 \(i\) に書き込む数字の \(k\) bit 目 (\(0 \leq k \leq N-1\)) を \(x_{k,i}\) とし，これを \(i\) について並べたベクトルを \(x_k = (x_{k,1},\dots,x_{k,N})\) とします．

各頂点について，それと隣接している頂点に書き込まれている整数の XOR が \(0\) であるという条件は，次のように表されます．

各 \(i=1,2,\dots,N\) と \(k=0,1,\dots,N-1\) について， \(\sum_{j=1}^N A_{ij} x_{k,j} = 0\)

この条件を行列積を用いて書き換えると次のようになります．

各 \(k=0,1,\dots,N-1\) について， \(Ax_k = 0\)

また，どの頂点に書き込まれる整数も \(0\) でないという条件は次のように表されます．

すべての \(i\,(1\leq i \leq N)\) について， \(x_{0,i},\dots,x_{N-1,i}\) の少なくとも1つは \(1\) である（すなわち，\(x_0,\dots,x_{N-1}\) の bitwise OR のすべての成分は \(1\) である）

以上より，\(Ax=0\) を満たすような \(0,1\) からなる \(N\) 次元ベクトル \(x\) を \(N\) 個選んで，どの成分にも少なくとも1つの \(1\) が含まれるようにできればよいです．

条件を満たす \(x_0,x_1,\dots,x_{N-1}\) の求め方

\(Ax = 0\) を満たすベクトル \(x\) は，XOR に関して閉じています．つまり， \(x,x'\) が \(Ax=0,Ax'=0\) を満たすならば， \(x''=x + x'\) で定まるベクトル \(x''\) も \(Ax''= 0\) を満たします．

XOR について閉じている \(N\) 次元の \(0,1\) からなるベクトルの集合 \(S\) には，基底が存在します．\(S\) の基底とは，以下を満たすベクトルの集合 \(B=\{b_1,b_2,\dots,b_m\}\) です．

• \(S\) の任意の元は，\(B\) からいくつかの元を選んで XOR を取ることで表すことができる
• \(B\) から \(1\) 個以上の元を選んで XOR を取ったとき，\(0\) になることはない

基底の要素数は \(N\) 以下です．

\(Ax=0\) を満たすベクトルの全体からなる集合 \(S\) の基底を \(b_1,b_2,\dots,b_m\) としたとき，これらの bitwise OR のすべての成分が \(1\) であれば，例えば \(x_0=b_1,x_1=b_2,\dots,x_{m-1}=b_m,x_m=x_{m+1}=\dots=x_{N-1}=0\) とすることで，条件を満たす \(x_0,x_1,\dots,x_{N-1}\) を得ることができます．逆に，基底の bitwise OR に \(0\) となる成分があれば，\(B\) のすべての元についてその成分は \(0\) であり，\(B\) の元の XOR として表される \(S\) のすべての元についてもその成分は \(0\) です．よって，この場合条件を満たすことは不可能です．

以上より，連立方程式 \(Ax=0\) の解集合の基底を求めることができれば，この問題を解くことができます．一般に，連立方程式 \(Ax=b\) の解は，掃き出し法というアルゴリズムによって \(O(N^3)\) 時間で求められます．このアルゴリズムは，以下の記事で詳細に説明されています．

• drken 氏による記事（日本語）：https://drken1215.hatenablog.com/entry/2019/03/20/202800
• cp-algorithms の記事（英語）：https://cp-algorithms.com/linear_algebra/linear-system-gauss.html

\(0,1\) からなる \(N\) 次元ベクトル \((N \leq 60)\) の元が 64-bit 整数で表現できることを利用して，\(O(N^2)\) 時間で掃き出すこともできます．