很容易发现条件其实就是限制二分图。
那么我们设 \(F(n,m)\) 表示 \(n\) 个点，\(m\) 条边组成二分图的答案（非简单图）。
那么答案可以发现是 \(F(n,m)\cdot2^m\) ，\(2^m\) 出自边的端点的两种顺序。
现在来计算 \(F(n,m)\) 。
我们这里的 \(m\) 很大，会达到 \(1e9\) 的级别，这时候很难用任何方法来计算（基本上的路子都用不了，只有次数不与 \(m\) 有关的多项式才能进行计算。）
会发现如果是简单图，那么 \(m\) 其实 \(\leq \lfloor\frac{n}{2}\rfloor\lceil\frac{n}{2}\rceil\) （记为 \(maxe(n)\) ） ，其他的边都是重复的。
那么此时我们就可以进一步写出式子：
\(F(n,m)=\sum_{i=0}^{maxe(n)}f(n,i)\cdot b(m,i)\)
\(b(m,i)\) 是把 \(m\) 条边分配到 \(i\) 条边上的方案。
容易发现 \(b(m,i)=i!{m\brace i}\) 。（因为此时相当于是 \(m\) 个球分配到 \(i\) 个互相区分的集合里。）
现在要计算 \(f(n,m)\) 。
这个东西是非联通简单二分图计数。
那如果我们能求出联通简单二分图计数 \(g(n,m)\)，再进行一次二元 \(exp\) 就可以求出\(f(n,m)\) 了。
考虑如何求 \(g(n,m)\) 。
设 \(h(n,m)\) 表示 \(n\) 个点，\(m\) 条边，对 \(n\) 个点黑白染色后，没有再同色点之间染色的方案数。
那么显然有 \(h(n,m)=\sum_{i=1}^n\binom{n}{i}\binom{i(n-i)}{m}\) 。
那么发现对 \(h\) 取 \(log\) 后再 \(/2\) 就是 \(g\) ，即 \(g=\frac{\log(h)}{2}\)
这是一个非常巧妙的一步。
我们将 \(h\) 进行了一些简单的变换过后，再进行 \(exp\) 操作后，得到的结果就不一样了，而此时如果正好可以进行简单计算，那么我们就将问题迎刃而解。
但是是如何想到 \(h(n,m)\) 这个东西的呢？
我们观察 \(f\) 和二分图，发现计算 \(f\) 的难点变在于划分左右域时会重叠的这一情况，这是非常难以进行容斥的。
那当我们通过一些手段使得消除划分这个限制之后，那问题就可以得到解决。
至于计算，众所周知的是取 \(\ln\) 是可以通过容斥dp来解决的：即
\(f_S=g_S-\sum_{S_1>S_2,S_1+ S_2=S} f_{S_1}\cdot g_{S_2}\)
而取 \(exp\) 则可以通过逆变换来解决，即：
\(g_S=f_S+\sum_{S_1>S_2,S_1+ S_2=S}g_{S_2}\cdot f_{S_1}\)
那么最后的式子即：
\(g_{n,m}=h_{n,m}-\sum_{x=0}^{n-1}\sum_{y=0}^m\binom{n-1}{x-1}g_{x,y}\cdot h_{n-x,m-y}\)
\(f_{n,m}=g_{n,m}+\sum_{x=0}^{n-1}\sum_{y=0}^m\binom{n-1}{x-1}g_{x,y}\cdot f_{n-x,m-y}\)
至此，我们解决了这个问题。
进一步的，我们可以发现
\[G=\frac{\ln(H)}{2} \]\[F=\exp(G)\\ \]\[F=\exp(\frac{\ln(H)}{2})=\sqrt H \]对于取根号,我们仍然有一个计数方法：
\(2f_S=g_S-\sum_{S_1+S_2=S,S_1\neq S,S_2\neq S} f_{S_1}f_{S_2}\)
那么此时就无须计算 \(g\) 了，我们可以直接计算得出 \(f\) 。
即：
\(f_{n,m}=h_{n,m}-\sum_{x=1}^{n-1}\sum_{j=0}^m \binom{n}{i}f_{x,y}\cdot f_{n-x,m-y}\)
那么此时就可以直接算出 \(f\) 了。
标签：abc327G,frac,计算,cdot,sum,exp,binom From： https://www.cnblogs.com/hawkrad/p/17810810.html