题解：AT_arc105_f [ARC105F] Lights Out on Connected Graph

· · 题解

两个约束条件：图联通和二分图。

考虑先满足第二个条件，并对于第一个条件进行容斥。

设 h_s 表示集合 s 为若干个二分图的方案数。对于每个集合 s，我们将其划分为不相交的两个集合 s_1,s_2，设两个集合之间的连边为 c 个，那么就有 2^c 种方案。对于所有划分求和即可。

不过上述求出来的有点小问题，就是一个有 k 个联通块的图会被计算 2^k 次。因为上述区分了黑白，一个联通块为一个二分图，可能左白右黑，也可能左黑右白是被统计了两次的。所以我们 考虑在区分黑白的意义下进行统计。

设 f_s 表示联通块 s 在区分黑白的意义下连成二分图的方案数。

那么根据经典图联通容斥，我们只需要用总方案数减去钦定 “最小点”所在联通块联通其他点任意的方案数即可。

最后注意需要答案除以 2，因为我们上面说了在区分黑白的意义下。

时间复杂度 O(3^n)。