(より詳しい解説は後日ブログで公開します)

まず連結な二部グラフの数え上げを考えます．これは，二部グラフの頂点を黒か白で塗ったものであって，同色を結ぶ辺がなく，最小ラベルの頂点が黒であるようなものを数えればよいです．なぜなら，非連結の場合は色の塗り方が偶数通りあり \({} \bmod 2\) で消えるからです．

\(n\) 頂点の連結二部グラフの重みの合計を \(f_n\) とすると，黒と白の頂点数で場合分けして，\(f_n = \displaystyle\sum_{i+j=n-1} \binom{n-1}{i} (1+A)^{(i+1)j}\) となります．\(A \ne 1\) のとき \((1+A)^{(i+1)j} = (1+A)^{\binom{i+1+j}{2}} (1+A)^{-\binom{i+1}{2}} (1+A)^{- \binom{j}{2}}\) を用いると畳み込みの形になっていて，二項係数の偶奇を考えると subset convolution になります．\(A = 1\) のときはすべての \(n \ge 1\) に対し \(f_n = 1\) です．

これを用いて連結とは限らない二部グラフを数えます．EGF \(f(x) = \sum_n f_n \dfrac{x^n}{n!},\, g(x) = \sum_n g_n \dfrac{x^n}{n!}\) を考えると，\(g(x) = \exp(f(x))\) です．ここで実際に \(n!\) で割ることはできないので，これらは形式的な記法です．逆数や \(\exp, \log\) も (定数項をそれぞれ \(1, 0, 1\) として) 係数に対する環演算で定義できます．\(\log(g(x)) - f(x) = 0\) について Newton 法を用いると \(g(x) \gets g(x) ( 1 + \log(g(x)) + f(x))\) という形で求まることがわかります．なお \(1/g(x) = g(x),\, \bigl( \log(g(x)) \bigr)' = g'(x) g(x)\) です．yhx-12243 さんによる資料も参考にしてください．

全体で，\(O(N \log(N)^2)\) 回の nim 積の計算を行うことになります．