この問題は 連結グラフ の数え上げにおけるテクニックをとりあげた問題です。
前提知識として、\(1,2,\dots,N\) からなる集合を整数 \(0,1,\dots,2^N-1\) に置き換えて bit 演算で DP を処理する bit DP と呼ばれるテクニックはここでは解説を省略します。

予備知識：部分集合の列挙

まず、この問題を解くには次の知識をあらかじめ知っておく必要があります。

非負整数 \(i,j\) に対して \(i\&j = j\) が成り立つとき、\(j \subseteq i\) と表すとする。 (ここで \(\&\) は bit ごとの論理積とする。)
このとき、 \(0 \leq i,j \lt 2^N, j \subseteq i\) を満たす \((i,j)\) の組を \(\mathrm{O}(3^N)\) で全て列挙することが出来る。

上の式だけを見ても目が回りそうなので、 \(N = 3\) のときの具体例を 2 進法表記 で以下に挙げると次のようになります。

• \(i = 000_{(2)} \to j = 000_{(2)}\)
• \(i = 001_{(2)} \to j = 000_{(2)}, 001_{(2)}\)
• \(i = 110_{(2)} \to j = 000_{(2)}, 010_{(2)},100_{(2)}, 110_{(2)}\)

これを見るとわかる通り、\(i,j\) は 「 \(j\) は \(i\) で立っているビットのみが立っている」という関係にあります。
これを \(i,j\) が表す集合の話に置き換えると、「 \(j\) は \(i\) に含まれる要素のみからなる」、すなわち「 \(j\) は \(i\) の部分集合である」と言い換えられます。
よって、上の \((i,j)\) の列挙とは、全ての \(i\) に対して \(i\) の部分集合を列挙する アルゴリズムに関する話だと分かります。

まずは条件を満たす \((i,j)\) が何個あるか考えてみましょう。
\(i\) の立っているビットの本数が \(k\) 本のとき、条件を満たす \(j\) は \(2^k\) 個あることに注目すると、 \((i,j)\) の組は

\[ \sum_{k=0}^N \binom{N}{k} 2^k\]

個あることが分かります。ここで二項定理を利用すると、上式は

\[ = (2 + 1) ^ N = 3^N\]

と変形できます。よって \((i,j)\) の組はちょうど \(3^N\) 個あることが示せました。

さて、実際に \((i,j)\) を列挙してみましょう。これは次のように \(i, j\) を全探索するナイーブなアルゴリズムで \(\mathrm{O}(4^N)\) で走査することができますが、 \(\mathrm{O}(3^N)\) 個を列挙するのに \(\mathrm{O}(4^N)\) かけるのは冴えません。

for (int i = 0; i < (1 << N); i++) {
  for (int j = i; j >= 0; j--) {
    if ((i & j) != j) continue;
    // (i, j) は条件を満たす
  }
}

実は以下のコードのように bit 演算を利用すると \(\mathrm{O}(3^N)\) で調べることが出来ます。

for (int i = 0; i < (1 << N); i++) {
  for (int j = i; j >= 0; j--) {
    j &= i;
    // (i, j) は条件を満たす
  }
}

\(3\) 行目に j &= i; としているのがポイントで、このように bitwise and を取ることで j の走査する範囲を \(\mathrm{O}(4^N)\) から \(\mathrm{O}(3^N)\) に減らしています。
以上より部分集合の列挙を \(\mathrm{O}(3^N)\) で行うことができました。このアルゴリズムを利用することでこの問題を解くことができます。

数え上げる対象を言い換える

さて、前提知識がそろったところで問題の解説に進みましょう。
まず、元の問題のままでは「\(1\) と \(k\) が連結」という条件が複雑で数えるのが困難に感じられます。このような場合は、対象を言い換えて計算可能な条件に変える必要があります。

以下では \(G\) の頂点集合を \(V := \lbrace 1,2,\dots,N \rbrace\) と表します。 \(S \subseteq V\) を満たす \(S\) に対して \(f(S), g(S)\) を次のように定めます。

• \(f(S) := \) \(S \subseteq V\) を頂点集合とする \(G\) の 連結部分グラフ の個数
• \(g(S) := \) \(S \subseteq V\) を頂点集合とする \(G\) の 部分グラフ の個数

次に、求めたい答えをグラフ理論の言葉で表すと「頂点 \(1\) と頂点 \(k\) が連結である \(G\) の全域部分グラフの個数」となりますが、これを \(C(k)\) と表して、 \(C(k)\) を \(f(S), g(S)\) で表すことを考えます。これは \(1\) と連結な頂点集合で場合分けをすると、

\[ C(k) = \sum_{\lbrace 1, k\rbrace \subseteq S \subseteq V} f(S) g(V \setminus S)\]

と表せることが確認できます。( \(V \setminus S\) は\(V\) から \(S\) を取り除いた集合です。)

よって、全ての \(S \subseteq V\) に対して \(f(S), g(S)\) を計算できれば上式を利用して\(\mathrm{O}(N 2^N)\) で \(C(2),\dots,C(N)\) を計算できます。

\(f(S)\), \(g(S)\) の計算

次は \(f(S), g(S)\) を計算してみましょう。
より容易に計算できるのは \(g(S)\) の方です。\(S\) に含まれる頂点間に張られている辺の本数を \(e\) 本としたとき、部分グラフの個数は \(2^e\) 個あることが確かめられます。よって、

• \(E(S) :=\) 辺の両端の頂点が \(S\) に含まれるような \(G\) の辺の本数

とおくと、 \(E(S)\) は全ての辺に対して \(S\) に含まれるかを判定すれば \(\mathrm{O}(M)\) で計算できます。よって全ての \(S \subseteq V\) に対して \(g(S)\) を \(\mathrm{O}(M 2^N)\) で計算することができました。

さて、最後に \(f(S)\) を計算しましょう。
\(f(S)\) は 包除原理 を利用した DP で計算することができます。 (これは余談ですが、以下に登場する DP は引き算しか登場しないことから一部の界隈では「除原理」や「除 DP 」と通称されているようです。)

\(S = \emptyset\) (\(\emptyset\) は空集合の意味。) の場合はあきらかなので \(S \neq \emptyset\) の場合を考えます。 \(f(S)\) を \(g(S)\) を用いて表すと、\(f(S) = g(S) - (\) 頂点集合が \(S\) である非連結なグラフの個数 \()\) と表せます。
この「非連結なグラフ」の部分を \(C(k)\) と同様の方法で \(f,g\) で表すことを考えます。 \(S\) に含まれる頂点を 1 つ取り出して \(v\) とすると、 \(v\) と連結な頂点集合で場合分けをすることで次の式を得ます。(\(T \subsetneq S\) は\( T \subseteq S\) かつ \(T \neq S\) の意味。)

\[ f(S) = g(S) - \sum_{v \in T \subsetneq S} f(T) g(S \setminus T)\]

よって部分集合を列挙するアルゴリズムを利用して \(f(S)\) を昇順に計算していくことで、全ての \(S \subseteq V\) に対して \(f(S)\) を \(\mathrm{O}(3^N)\) で求めることができます。

以上より \(f(S), g(S)\) を計算できたので、あとはさきほどの式に代入することでこの問題を \(\mathrm{O}(3^N)\) で解くことができます。

なお、 \(g(S)\) は 高速ゼータ変換 と呼ばれるアルゴリズムを利用して \(\mathrm{O}(N 2^N)\) で計算できることが知られていますが、 G 問題を解く上ではナイーブなアルゴリズムで十分なのでここでは取り上げませんでした。
高速ゼータ変換も重要な DP のテクニックなので、興味がある方は「高速ゼータ変換」「Sum over Subset DP」などの単語で検索してみることをおすすめします。
また、\(f(S)\) は高度なアルゴリズムを利用して \(\mathrm{O}(N^2 2^N)\) で計算できることが知られていますがここでは割愛します。

類題

• AOJ2345: Network Reliability