首页 > 其他 > 详细

[状压DP思路妙题]图

时间:2020-01-23 12:14:26      阅读:63      评论:0      收藏:0      [点我收藏+]
  • 源自 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

  • 咕咕咕

[状压DP思路妙题]图

原文:https://www.cnblogs.com/xyz32768/p/12230423.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!