Just as we found in Problem D, the answer to this problem equals \(2^M\) times the answer to the following problem:

Find the number of (not necessarily simple) bipartite graphs with \(N\) vertices and \(M\) edges. Here, the vertices are labeled from \(1\) through \(N\), and the edges from \(1\) through \(M\).

Here, we let \(a(N, M)\) be the answer to the problem above, and describe how to find \(a(N, M)\) fast enough.

Boiling down to counting simple bipartite graphs

In fact, evaluating \(a(N, M)\) can be boiled down to counting (vertex-labeled) simple bipartite graphs.

For each graph to be counted in \(a(N, M)\), there is one corresponding simple bipartite graph by identifying multiple edges. Also, if we let

• \(b(M, k)\) : the number of ways to put \(M\) distinguishable balls to \(k\) boxes,

then for each simple bipartite graph with \(k\) edges, exactly \(b(M, k)\) graphs are counted in \(a(N, M)\). Thus,

• \(f(N, M)\) : the number of vertex-labeled simple bipartite graphs with \(N\) vertices and \(M\) edges

satisfies

\[a(N, M) = \sum_{k=0}^{L}f(N, k) b(M, k),\]

where \(L = \lfloor N/2 \rfloor \lceil N/2 \rceil\) (\(=\) maximum edges in an \(N\)-vertex bipartite graph). What is more, \(b(M, k)\) equals \(M!\) times the Stirling number of the second kind, \(S(M, k)\), so it can be expressed as

\[b(M, k) = \sum_{i=1}^k (-1)^{k-i} \binom{k}{i} i^M.\]

Therefore, \(b(M, \ast)\) can be enumerated in a total of \(\mathrm{O}(N^4 \log M)\) time.

Hence, we can evaluate \(a(N, M)\) once we enumerate \(f(N, 0), f(N, 1), \dots, f(N, L)\).

Counting simple bipartite graphs

One can enumerate \(f(N, 0), f(N, 1), \dots, f(N, L)\), i.e. count simple bipartite graphs, by a DP (Dynamic Programming) informally called “exclusion-principle DP.” See also the editorial of ABC213 for an explanation on the exclusion-principle DP.

First, define \(g(n, m)\) \((1 \leq n \leq N, 1 \leq m \leq L)\) as follows:

• \(g(n, m) :=\) (the number of simple graphs with \(n\) vertices and \(m\) edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).

Then \(g(n, m)\) can be computed by:

\[g(n, m) = \sum_{i=0}^n \binom{n}{i} \binom{i(n-i)}{m}.\]

Next, we perform DP to impose connectivity.
Define \(h(n, m)\) \((1 \leq n \leq N, 1 \leq m \leq L)\) by adding “connected” constraints to the definition of \(g\):

• \(g(n, m) :=\) (the number of simple connected graphs with \(n\) vertices and \(m\) edges, where each vertex is painted either white or black, and no edge connects vertices with the same color).

Then, the idea of exclusion principle yields the following expression, enabling us to evaluate \(h(n, m)\) in ascending order of the indices with DP:

\[h(n, m) = g(n, m) - \sum_{1 \leq i \lt n} \sum_{0 \leq j \leq m} \binom{n-1}{i-1} h(i, j) g(n-i,m-j).\]

Noticing that every simple connected bipartite graph is counted twice in \(h\), we obtain:

• \(\dfrac{h(n, m)}{2} =\) (the number of simple connected bipartite graphs).

Thus, after dividing all \(h(n, m)\) by two, we can perform a DP that is an inverse of the exclusion-principle DP in order not to impose connectivity. Specifically, use the recurrence relation

\[f(n, m) = \frac{h(n,m)}{2} + \sum_{1 \leq i \lt n} \sum_{0 \leq j \leq m} \binom{n-1}{i-1} f(i, j) \frac{h(n-i,m-j)}{2}\]

to perform the aforementioned DP but in the opposite direction.

Therefore, we have enumerated \(f(N, 0), \dots, f(N, L)\). The complexity is \(\mathrm{O}(N^6)\), but there is a constant factor of \(1/64\), so this is fast enough.

Hence, the problem has been solved in a total of \(\mathrm{O}(N^6 + N^4 \log M)\) time.

Bonus 1: interpretation by generating function

The relation between \(f(n, m)\) and \(g(n, m)\) can be justified alternatively by two-variable generating function.
Consider two-variable generating functions of exponential type with respect to vertices and of ordinary type with respect to edges. Define \(F\), \(G\), and \(H\) as follows:

\[F(x, y) = 1 + \sum_{n,m} \frac{x^n y^m}{n!} f(n, m)\]

\[G(x, y) = 1 + \sum_{n,m} \frac{x^n y^m}{n!} g(n, m)\]

\[H(x, y) = \sum_{n,m} \frac{x^n y^m}{n!} h(n, m)\]

In fact, the exclusion-principle DP corresponds to computing \(\log\), and its inverse to computing \(\exp\); so the two DP is equivalent to evaluating

\[H = \log(G), F = \exp\left(\frac{H}{2} \right).\]

Here is why: as for \(H=\log(G)\), we have

\[\exp(H)=G \to G\frac{\partial H}{\partial x} = \frac{\partial G}{\partial x};\]

comparing the coefficients of some degree yields the same recurrence relations as described above. (The inverse also holds.)
Composing two equations, we obtain an unexpectedly simple relation between \(F\) and \(G\):

\[F^2 = \exp \left(\frac{\log(G)}{2} \times 2 \right) = G.\]

The combinatoric interpretation of \(F^2 = G\) may be like:

• \(G =\) (the generating function of the object of \(g\))
  \(=\) (the generating function of graphs whose vertex with the smallest index is painted black) \(\times\) (the generating function of graphs whose vertex with the smallest index is painted white)
  \(=\) \(F \times F\)

(Perhaps it is also possible to exploit this interpretation to derive a DP to compute \(F\) from \(G\).) Such \(F\) against \(G\) (the square root whose constant term is \(1\)) is called the square root of a formal power series, denoted by \(F = \sqrt{G}\).

Bonus 2: another solution

We briefly introduce another way to solve it.
As we already defined, let \(L := \lfloor N/2 \rfloor \lceil N/2 \rceil\). With the same DP as above, the first \((L+1)\) terms \(a(N,0), a(N, 1), \dots, a(N, L)\) for a fixed \(N\) can be enumerated, whose details we omit.
Also, for a fixed \(N\), the generating function of the answer can be expressed as

\[\sum_{m \geq 0} a(N, m) x^m = C + \frac{P(x)}{(1-x)(1-2x)\dots (1-Lx)}\]

with a constant \(C\) and a polynomial \(P(x)\) of degree \((L-1)\) or less. (This is justified by the discussion above and by the fact that the Stirling numbers \(S(N,k)\) \((k \leq L)\) can be represented as a linear combination of \(0^M, 1^M, \dots, L^M\).) By this fact, \(a(N, 1), a(N, 2), \dots\) (but not \(a(N, 0)\)) is not affect by \(C\), and can be represented by a linear recurrence relation of the \(L\)-th order. Therefore, one can reconstruct \(C\) and \(P(x)\) from the values \(a(N,0),a(N,1)\dots,a(N,L)\) and then evaluate \(\lbrack x^M \rbrack \frac{P(x)}{(1-x)(1-2x)\dots (1-Lx)}\) using Bostan-Mori algorithm to find \(a(N, M)\). (For Bostan-Mori algorithm, see also the editorial of ABC300 Ex.) Even if you do not realize the fact, one can still experimentally assert the linear recursivity using Berlekamp-Massey algorithm and get AC.