[DP记录]ARC105F Lights Out on Connected Graph
command_block
2021-10-26 10:04:28
**题意** ： 给出一张 $n$ 个点 $m$ 条边的无向图 $G$。
对于一张图，定义它是好的，当且仅当：
- 图联通
- 初始时将边染成白色，通过（多次）翻转某个点的所有邻边颜色，可以将所有边变为黑色
我们将 $G$ 的 $m$ 条边保留一个子集，共有 $2^m$ 种方法，问其中多少种形成的图是好的。
答案对 $998244353$ 取模。
$n\leq 17$ ，时限$\texttt{3s}$。
------------
首先考虑如何判定一张图是否为好图。
相当于存在一个点集，使得每条边都恰有一端在点集内。由此容易发现， $G$ 是好的当且仅当 $G$ 是连通二分图。
于是本题就变为计算生成联通二分图数目。
记 $f_S$ 为 $S$ 内形成联通二分图，并黑白染色的方案数，$g_S$ 为 $S$ 内形成二分图（不要求联通），并黑白染色的方案数。
最终的答案就是 $f_{\{1\sim n\}}/2$。
对于 $f$ ，考虑用全部情况减去不连通的情况，任取一个元素 $u\in S$ ，枚举 $u$ 所在的联通块。
$$f_S=g_S-\sum\limits_{u\in T\subseteq S}f_Tg_{S-T}$$
（这里需要加入 $T,S-T$ 之间的边，但是都必须删除，故方案数系数为 $1$）
对于 $g$ ，直接枚举黑白染色方案，求有多少种可能的断边方案。两端同色的边必须断，其余边可断可不断，方案数是 $2$ 的幂。
需要辅助数组 $l_S$ 表示 $S$ 内部的边数。
复杂度 $O(3^n+2^nm)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxS 133000
using namespace std;
const int mod=998244353;
int n,m,pw2[105],f[MaxS],g[MaxS],l[MaxS];
int main()
{
scanf("%d%d",&n,&m);
int lim=(1<<n)-1;
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);u--;v--;
int S=lim^(1<<u)^(1<<v);
for (int T=S;;T=(T-1)&S){l[lim^T]++;if (!T)break;}
}
pw2[0]=1;for (int i=1;i<=m;i++)pw2[i]=(pw2[i-1]<<1)%mod;
for (int S=1;S<=lim;S++){
int S2=S^(S&-S);
for (int T=S2;;T=(T-1)&S2){
g[S]=(g[S]+pw2[l[S]-l[T]-l[S^T]])%mod;
f[S]=(f[S]+1ll*f[S^T]*g[T])%mod;
if (!T)break;
}g[S]=(g[S]<<1)%mod;
f[S]=(g[S]+mod-f[S])%mod;
}printf("%d",1ll*f[lim]*(mod+1)/2%mod);
return 0;
}
```