arc115D odd degree

statement

题意很简洁。

让你对于 \(k\in[1,n]\) 求一个图有多少个子图有恰好 \(k\) 个奇度的点。

\(n,m\leq 5000\)。

注意子图特殊定义：原图 \(E\),子图 \(S\)。\(E,S\) 点集相同，\(S\) 边集是 \(E\) 边集的子集。

---

solution

这个题其实和 cf1515G 有异曲同工之妙。

这道题本质让我们决策每一条边选还是不选。

hint1

如果是树怎么办？

key

接下来就是最精妙的地方了！

在树上的时候，只要我们钦定奇度点，我们可以得到唯一边的决策情况。

可以从反证法，如果多一条边，那么必须用一个环来抵消，树中没有环。

若要 \(2\mid k\) 个奇度点，则方案数就为 \(\binom{n}{k}\)。

---

从而可以扩展到平凡图。

我们拉出来一棵生成树，然后我们先决策树边，接下来决策非树边。

现在本质上是对一个树边的决策情况，我们想把若干个环取反使得奇偶状态不变。

这里与 cf1515G 便十分相似，我们认为每一个非树边与树边形成的简单环是所有环的“基环”。

所以只需要随意决策每一个非树边选不选即可。

---

也可以这么理解无论我们怎么决策非树边 \((x,y)\)，都可以通过把 \(x,y\) 间树边取反，使得状态不变。

\(\texttt{Complexity : }\mathcal{O(n\alpha(n)+n^2)}\)。

code