ハミルトン路の個数 (bitmask DP) Java編（paizaランク A 相当）

グラフ上の任意の頂点から出発し、すべての頂点をちょうど 1 回ずつ訪問することができるようなグラフを準ハミルトングラフといいます。また、そのような順番で頂点を並べたパスをハミルトン路といいます。

n 頂点 m 辺の有向グラフが与えられます。i 番目の辺は頂点 a_i から頂点 b_i に向かっています。なお、グラフは自己ループや多重辺を含みません。

このグラフにハミルトン路がいくつ存在するか求めてください。
なお、頂点の並びが少しでも異なるものは別のハミルトン路として数えてください。
(a_i ≠ b_i であるような i が存在するとき、ハミルトン路 (a_1, a_2, ..., a_n) と (b_1, b_2, ..., b_n) は別のハミルトン路として数えてください。)

今回は n が最大で 18 と、全探索では間に合わないサイズになっています。そのため、bitmask DP を用いて解く必要があります。

ここで、以下のように DP テーブルを定義します。
DP[S][v] := 頂点集合 S に含まれる頂点をすべて訪問した状態で頂点 v にいるようなパスの個数 (ただし、S は集合の bitmask を整数で表現したものとします)

このとき、DP[S][v] から以下のように遷移することで、DP テーブルを更新することができます。
DP[S + 2^u][u] += DP[S][v] (u は S に含まれていない頂点で、辺 (v, u) が存在し、v ≠ u)

これをすべての S, v, u について実行し、最終的に DP[2^n - 1][v] (0 ≦ v < n) の総和を求めることで、答えを求めることができます。

なお、DP[2^v][v] (始点だけを訪問した状態) を 1 (0 ≦ v < n) で、それ以外を 0 で初期化する必要があります。
また、bitmask の集合表現では番号が 0 から始まることに注意しましょう。

この問題では、答えが符号付き 32 bit 整数に収まらない場合があるので注意してください。答えが符号付き 64 bit 整数に収まることは保証されています。