BZOJ 4671:异或图题解

主要思路

我们发现,直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算:划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算,可以考虑 DFS 枚举出每一个点所在的连通块根,然后把连通情况放入线性基中,如果线性基插入失败,那么说明当前的情况不能被表示出,且该状态符合划分,那么计入小答案\(tot\),最后对答案的贡献就是:\(2^{tot}\)。

现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数,使得\(f(i)\)只被计算一次:

\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]

打表出来就是:

\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]

继续阅读BZOJ 4671:异或图题解