This problem is about techniques on combinatorics on connected graph.
As a prerequisite, we do not explain the technique called bit DP (DP=Dynamic Programming) in which each integer \(0,1,\dots,2^N-1\) is regarded a subset of \(1,2,\dots,N\).

Prerequisite: subset enumeration

Firstly, the following knowledge is required to solve this problem:

For any non-negative integers \(i\) and \(j\), if \(i\&j = j\), let us denote \(j \subseteq i\). (Here, \(\&\) is bitwise logical products.)
Then, the pairs \((i, j)\) such that \(0 \leq i,j \lt 2^N, j \subseteq i\) can be enumerated in a total of \(\mathrm{O}(3^N)\) time.

The equations above make us dizzy, so let us show you the example for \(N = 3\) in a binary notation:

• \(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)}\)

As you can see, \(i\) and \(j\) are in the relationship where “a bit in \(j\) has the value \(1\) only if the corresponding digit in \(i\) has the value \(1\).”
The counterpart for the sets represented by \(i\) and \(j\) are “all elements in \(j\) are in \(i\),” that is, “\(j\) is a subset of \(i\).”
Therefore, now we can understand that the enumeration of \((i, j)\) described above is about the algorithm of enumerating all the subset of \(i\) for every \(i\).

First, let us count how many pairs \((i,j)\) satisfies the conditions.
If \(i\) has \(k\) ones in its binary notation, the number of \(j\) satisfying the conditions are \(2^k\); so the number of pairs \((i, j)\) is

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

Here, we can apply binomial theorem to obtain

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

Therefore, we have proved that the number of pairs \((i,j)\) are exactly \(3^N\).

Now let us actually enumerate \((i,j)\). They can be enumerated in a total of \(\mathrm{O}(4^N)\) with the following naive brute-force algorithm, but spending \(\mathrm{O}(4^N)\) time for iterating through \(\mathrm{O}(3^N)\) elements is not cool.

for (int i = 0; i < (1 << N); i++) {
  for (int j = i; j >= 0; j--) {
    if ((i & j) != j) continue;
    // (i, j) satisfies the condition
  }
}

Actually, we can exploit the bit operation as follows to enumerate them in a total of \(\mathrm{O}(3^N)\) time.

for (int i = 0; i < (1 << N); i++) {
  for (int j = i; j >= 0; j--) {
    j &= i;
    // (i, j) satisfies the condition
  }
}

The key point is j &= i; in the third line. By taking bitwise and like this, the volume of range of j is decreased from \(\mathrm{o}(4^N)\) to \(\mathrm{o}(3^N)\).
Therefore, we can enumerate the subsets in a total of \(\mathrm{O}(3^N)\) time. We can use this algorithm to solve the problem.

Rephrase what we want to count

Now we have enough prerequisite; let us explain the original problem.
First, the condition “\(1\) and \(k\) are connected” in the original problem seems to be too complex to count. In that case, we want to rephrase the object so that it becomes computable.

Let \(V := \lbrace 1,2,\dots,N \rbrace\) be the set of vertices in \(G\). For \(S\) such that \(S \subseteq V\), we define \(f(S)\) and \(g(S)\) as follows:

• \(f(S) := \) The number of connected subgraph of \(G\) whose vertex set is \(S \subseteq V\)
• \(g(S) := \) The number of subgraph of \(G\) whose vertex set is \(S \subseteq V\)

Next, the desired answer can be rephrased in terms of graph theory as “the number of spanning subgraph of \(G\) such that Vertex \(1\) and Vertex \(K\) are connected;” let us denote it by \(C(k)\), and consider how to represent it by \(f(S)\) and \(g(S)\). The cases can be divided by the set of vertices that are connected to \(1\), so we have

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

(\(V \setminus S\) denotes the set of elements of \(V\) except for those in \(S\).)

Therefore, if we can compute \(S \subseteq V\) for all \(f(S), g(S)\), then we can compute \(C(2),\dots,C(N)\) in a total of \(\mathrm{O}(N 2^N)\) with the equation above.

Computing \(f(S)\) and \(g(S)\)

Now, how can we compute \(f(S)\) and \(g(S)\)?
The easier to compute is \(g(S)\). Let \(e\) be the number of edges that connects the vertices in \(S\), then the number of subgraphs is \(2^e\). Thus, let

• \(E(S) :=\) the number of edges of \(G\) whose vertices on both ends are included in \(S\),

then \(E(S)\) can be computed in a total of \(\mathrm{O}(M)\) time by checking if each edge is included in \(S\). Therefore, for every \(S \subseteq V\), we have found \(g(S)\) in a total of \(\mathrm{O}(M 2^N)\) time.

Finally, let us compute \(f(S)\).
\(f(S)\) can be solved with a DP using inclusion-exclusion principle. (By the way, the DP described below is said to be “exclusion principle” or “exclusion DP” by some people, as only subtraction is used.)

\(S = \emptyset\) (\(\emptyset\) denotes an empty set) is trivial, so we assume \(S \neq \emptyset\). \(f(S)\) can be represented by \(g(S)\) as \(f(S) = g(S) - (\) the number of unconnected graph with vertex set \(S\) \()\).
Let us represent this “unconnected graph” part by \(f\) and \(g\) just as we did for \(C(k)\). Let \(v\) be a vertex in \(S\), then we can divide the cases by the connected component including \(v\) by the following expression. (\(T \subsetneq S\) means \( T \subseteq S\) but \(T \neq S\).)

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

Therefore, we can compute \(f(S)\) in the increasing order, using the algorithm of enumerating the subsets, so that we obtain \(f(S)\) for all \(S \subseteq V\) in a total of \(\mathrm{O}(3^N)\) time.

Note that \(g(S)\) can be computed by an algorithm called Fast Zeta Transform in a total of \(\mathrm{O}(N 2^N)\) time, but for solving Problem G, naive algorithm is enough, so we didn’t introduce it here.
Fast Zeta Transform is another important DP technique, so if you are interested, search on the Internet for the words like “Fast Zeta Transform” or “Sum over Subset DP”.
Also, a faster algorithm of finding \(f(S)\) in a total of \(\mathrm{O}(N^2 2^N)\) time is known, but we will omit it.

Similar problem

• AOJ2345: Network Reliability