sugarrrさんによる公式解説を、私にとって読みやすいように書き換えたものです。新規性はありません。

イメージは半分全列挙です。

bitwise xorの記号と論理xorの記号をともに \(\oplus\) で表します。また、\(X_i\) が真偽値のとき \(\sum X_i\) で、「\(X_i\) が \(\text{True}\) であるようなものの個数」を表します（真を\(1\)、偽を \(0\) としてとった和）

頂点集合を互いに素な \(V_1,V_2\) の \(2\) つ分けます。

\(D_1[S]=\) \(V_1\) の部分集合 \(S\) について、\(S\) にカメラを置いたとき、監視される辺の個数が奇数か？(bool)
\(D_2[T]=\) \(V_2\) の部分集合 \(T\) について、\(T\) にカメラを置いたとき、監視される辺の個数が奇数か？(bool)
\(D_3[S][T]=\) \(V_1\) の部分集合 \(S\)、\(V_2\) の部分集合 \(T\) について、\(S,T\) にカメラを置いたとき、\(S\) と \(T\) を結ぶ道のうち、監視される辺の個数が奇数か？(bool)
とそれぞれおきます。

\(V_1,V_2\) のうちカメラをおく頂点集合をそれぞれ \(S,T\) に決めたとき、監視される辺の個数は包除原理により「\(S\)から監視される辺の個数」＋「\(T\) から監視される辺の個数」－「\(S,T\) 両方から監視される辺の個数」です。

したがって、「\(S,T\) にカメラを置いたとき、監視される辺の個数は奇数か？」は \(D_1[S]\oplus D_2[T]\oplus D_3[S][T]\) に等しくなり、元の問題の答えは
\(\displaystyle 2^N - \sum_{S,T} D_1[S]\oplus D_2[T]\oplus D_3[S][T]\)
となります。\(D_1,D_2\) は\(O(N^2 2^{N/2})\) 時間で愚直に求めることが可能です。\(D_3\) はサイズ \(2^N\) の表なので、制限時間内に全てを求めることはできません。\(D_3\) を計算することなく元の問題に答える方法を考えます。

\(D_3[S][T]=\bigoplus_{t\in T}D_3[S][\{t\}]\) であり、\(D_3[S][\{t\}]=\text{True}\) である \(t\) だけが和に寄与するので
\(f(S)=\{t\in V_2 \mid DP3[S][\{t\}]=\text{True}\}\) とすると \(D_3[S][T]=\text{is\_odd}(f(S)\cap T)\) になります。（\(\text{is\_odd}(X)\) は有限集合 \(X\) の要素数が奇数のとき \(\text{True}\)、偶数のとき \(\text{False}\) を返す）

したがって
\(\sum_{S,T} D_1[S]\oplus D_2[T]\oplus D_3[S][T] =\sum_{S,T} D_1[S]\oplus D_2[T]\oplus \text{is\_odd}(f(S)\cap T)\)
となります。 \(f\) は\(O(N^2 2^{N/2})\) で前計算できるため、和の計算に必要なデータは \(O(N^2 2^{N/2})\) で用意することができました。しかし、和をとる対象の \((S,T)\) の組が \(2^N\) 個あるので、まだそのまま計算することはできません。こういうときは、たいてい一方の変数に関してだけ先に和を取る方法がうまくいきます。

\(\displaystyle g(T')=\sum_T D_2[T]\oplus \text{is\_odd}(T'\cap T)\)

とおくと、

\(\displaystyle \sum_{S,T} D_1[S]\oplus D_2[T]\oplus \text{is\_odd}(f(S)\cap T) =\sum_{D_1[S]=\text{False}} g(f(S)) + \sum_{D_1[S]=\text{True}}(2^{|V_2|} - g(f(S)))\)

となります。

これは \(f,g\) が求まっていれば、実際に \(O(2^{N/2})\) 個の \(S\) についてそれぞれの値を求めることで計算できるので、あとは \(g\) が計算できればOKです。

\(g\) は \(O(N 2^{N/2})\) で求めることができることを以下で確かめます。\(V_2\) の頂点集合に改めて番号を振り直し \(0,1,\ldots |V_2|-1\) とし、 \(V_2\) の部分集合と \(0\) 以上 \(2^{|V_2|}-1\) 以下の整数を同一視します。また真偽値を0,1と同一視します。

\(g\) の計算式を行列の形に書き直すと次のようになります。

\( \begin{pmatrix} g(0)\\ g(1)\\ \vdots\\ g(2^{|V_2|}-1) \end{pmatrix} = \begin{pmatrix} D_2[0]\oplus\text{is\_odd}(0\cap 0) & D_2[1]\oplus \text{is\_odd}(0\cap 1) &\dots & D_2[2^{|T|}-1]\oplus \text{is\_odd}(0 \cap 2^{|T|}-1)\\ D_2[0]\oplus \text{is\_odd}(1\cap 0) & D_2[1]\oplus\text{is\_odd}(1\cap 1) &\dots & D_2[2^{|T|}-1]\oplus\text{is\_odd}(1 \cap 2^{|T|}-1)\\ \vdots & \vdots & \vdots & \vdots \\ D_2[0]\oplus \text{is\_odd}(2^{|T|}-1 \cap 0) & D_2[1]\oplus\text{is\_odd}(2^{|T|}-1\cap 1) &\dots & D_2[2^{|T|}-1]\oplus\text{is\_odd}(2^{|T|}-1 \cap 2^{|T|}-1)\\ \end{pmatrix} \begin{pmatrix} 1\\ 1\\ \vdots\\ 1 \end{pmatrix} \)

ここで、\((i,j)\) 成分が \(\text{is\_odd}(i\cap j) \) からなる行列は アダマール変換に用いられるアダマール行列 と同様の再帰構造を持ち、したがって、\((i,j)\) 成分が \(D_2[j]\oplus \text{is\_odd}(i\cap j) \)である上述の行列も同様の再帰構造を持ちます。

よって、高速アダマール変換と同様のアルゴリズムにより、ベクトルとの積を高速に計算することができます。すなわち、全ての\(i\) に対する \(g(i)\) を \(O(|V_2|2^{|V_2|})\) で求めることができるとわかりました。