[状压DP思路妙题]图

2024-10-08 05:39:56

源自 luhong 大爷的 FJ 省冬令营模拟赛题

Statement

给定一个 \(n\) 个点 \(m\) 条边的图，没有重边与自环
每条边的两端点编号之差不超过 \(12\)
求选出一个非空点集使其导出子图连通的方案数模 \(2\) 后的结果
\(n\le 50\)，\(m\le\binom n2\)

Solution

妙啊！！！\(\times 3\)
首先我们注意到：对于一个非空图，\(2^{连通块个数}\equiv[图是否连通]\times 2(\bmod 4)\)
于是考虑转化成对于所有的点集，计算出 \(2^{连通块个数}\) 的和 \(\bmod 4\) 的结果
由于 \(2|4\) ，且空集的贡献为 \(1\)，所以上面的结果除以 \(2\) 下取整后就是答案
~~看上去好像好像更不好做~~
考虑组合意义：对选出的所有点黑白染色，使得任意边的两个端点颜色相同的方案数
由于边两端点之差不超过 \(12\)，可以有一个 DP：\(f[i][S]\) 表示前 \(i\) 个点，最后 \(11\) 个点的状态为 \(S\)（三进制数，储存白/黑/不在点集内三种情况）
转移枚举下一个点的状态即可
\(O(n\times3^{11})\)

Code

咕咕咕

最新文章

热门文章