ARC105F Lights Out on Connected Graph

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给出一张 个点 条边的无向图 。

对于一张图，定义它是好的，当且仅当：

  • 图联通

  • 初始时将边染成白色，通过（多次）翻转某个点的所有邻边颜色，可以将所有边变为黑色

我们将 的 条边保留一个子集，共有 种方法，问其中多少种形成的图是好的。

答案对 取模。

，时限 。

首先考虑如何判定一张图是否为好图。

相当于存在一个点集，使得每条边都恰有一端在点集内。由此容易发现， 是好的当且仅当 是连通二分图。

于是本题就变为计算生成联通二分图数目。

记：

  • ：点集 内形成联通二分图，并黑白染色的方案数。
  • ：点集 内形成二分图（不要求联通），并黑白染色的方案数。

答案是 。

对于 ，用全部情况减去不连通的情况，任取一个元素 ，枚举 所在的联通块。

（这里需要新考虑 之间的边，它们都必须删除，故方案数系数为 ）

对于 ，直接枚举黑白染色方案，求有多少种可能的断边方案。两端同色的边必须断，其余边可断可不断，方案数是 的幂。需要辅助数组 表示 内部的边数。复杂度和枚举子集一致。

复杂度 。