サイクル基底

まず直感的な説明をします。サイクルを2つ書いて、辺のxorをとってください。辺のxorとは、2つのサイクルが同じ辺を共有している場合その辺を削除するということです。そうすると新しいサイクル(正しくはオイラリアンなグラフ。つまり全頂点の次数が偶数。非連結になっちゃうこともあるので)ができますよね。グラフのサイクル(正しくはオイラリアンな部分グラフ)をすべて考えたいときに、いくつかサイクルを用意して、それらのサイクルをxorすることによってそれを全部考えようというのがサイクル基底のアイデアです。では、どのようなサイクルの集合(基底)を考えればいいのでしょうか。

$n$ 頂点 $m$ 辺, $c$ 連結成分のグラフを考えます。全域森を考えると、 $m - n + c$ 本の辺が全域森に含まれません。これら全域森に含まれない辺のそれぞれについて、その辺と全域森の辺のみからなる閉路があります。これらの閉路の集合がサイクル基底になります。

使い道

サイクル基底のアイデアは上のとおりですが、実際に扱うときは、 $m$ 次元ベクトルで、 $i$ 番目の要素はそのサイクルが $i$ 番目の辺を含むとき1, そうでないとき0としたものとして扱うことが多いようです。

サイクルの個数カウント

一般にサイクル基底で適当にxorをとったものはオイラリアンになります。今回解いた問題では、サイクル(各頂点を1度しか通らないようなもの)を列挙するのですが、今回の問題ではサイクル基底の個数がたかだか16なので、実際にサイクルを(1 << 16)個を全列挙し、そのうち同じ頂点を一度しか通らないものをチェックするという方針で解けます(サイクルの全列挙には、縮約の前処理が必要です。計算量が指数なので一般のグラフだとできないと思う)。

stパスのカウント

stパスと(サイクル基底を適当にxorしたもの)もstパスになります。tex: XOR回廊みたいな、パスのコストが辺のコストのxorで決まる問題との相性がすごいです。XOR回廊はまんま、stコストの最大値を求めたいわけですが、これを知っているとxorのGauss Jordan Eliminationに持ち込むだけになります。

サイクルの個数(bitdpで)

上述したようにサイクル基底でもどうにかなりそうです。ただ、今回のように同じ頂点を1度しか通ってはいけないという制約の場合、bitdpで解くこともできます。ぼくたちはサイクル基底を知らなかったのでこうしました(追記: と思ったんですが、頂点数が16程度ならこの方針で解けるんですが、実際は頂点数は50程度になることもあって無理でした)。

具体的には辺を一本ずつ追加していきます。辺 $(u, v)$ を追加するとき、新たに増えるサイクルの個数は $(u, v)$ を通るサイクル、つまり追加前のグラフにおける $(u, v)$ パスの本数です。これはdp[S][v]: 頂点集合Sを回っていまvにいるときの場合の数を計算すればできるので、bitdpを辺の本数分やれば求まります。こっちのほうが思考停止でできるのでよさそうな気がします。