给定一张 $n$ 个点，$m$ 条边的无向简单图 $G = (V, E)$，对于 $E$ 的子集 $S$，我们把所有与 $E$ 中至少一条边相邻的点构成的集合称为 $V(S)$，$S$ 被称为好的当且仅当：
设所有与 $S$ 中大于一条边相邻的点的数量为 $w$，那么边集 $S$ 的权值为 $2^w$。
现在，你需要对 $E(G)$ 的所有子集，求出所有好的子集的权值和。
第一行包含两个正整数 $n, m$ ($n \leq 16; m \leq \dbinom n2$)，含义如题意所述。
接下来的 $m$ 行，第 $i$ 行包含两个整数 $x_i, y_i$ ($1 \leq x_i, y_i \leq n; x_i \neq y_i$)，表示 $x_i$ 与 $y_i$ 之间有一条无向边。
输出一行一个整数，表示好的子集的权值和对 $998244353$ 取模的值。
先来分析什么样的边集 $S$ 是好的边集。
由性质 2，$S$ 导出的子图 $G[S]$ 必须是连通的。否则，在不同的连通块取点，就不存在所有边都在 $S$ 中的路径。
又由性质 1，$S$ 导出的子图具有相等的点数和边数。
因此，图 $G' = \left( V(S), S \right)$ 为一个具有相等的点数和边数的连通图，从而得知，$G$ 是基环树。
对于一个好的边集 $E$ (即 $G$ 的子基环树 $B$)，它的权值又等于多少呢？
在 $B$ 中，只与一条边相邻的顶点，即度为 $1$ 的节点，一定是 $B$ 的外向树的叶节点。因此 $w$ 就等于 $B$ 中非叶节点的节点数，然后权值即为 $2^w$。
注意到基环树不像树一样可以直接 DP，它首先有一个环。我们先考虑如何处理掉这个环。
注意到环上的节点不可能是叶节点，因此对于答案之和构成环的是哪些点有关，与这些点内部是如何连接的无关。因此只要确定了构成环的点集，接下来的事情就与环内部无关了。
因此，第一个问题是，给定一个点集 $V_0$，如何求出由 $V_0$ 中所有点构成的环的数目。你需要对所有 $V_0 \subseteq V$ 给出答案。
对，就是环计数问题，状态压缩 DP 入门练习题。具体做法我就不再赘述了，可以参考 [Codeforces11D]A Simple Task，通过最小数原理进行 DP。
最后，如果 $c > 2$ 且链的两端连通，就可以说明集合 $V_0$ 中就有对应数量的环。记得最后别忘记将 $\mathrm{cycle}(V)$ 乘 $\dfrac 12$。
接下来，我们来考虑对于给定的 (构成环的) 节点集合 $V_0$，如何统计这些基环树的权值和。
发现直接做不好做，因此我们先从统计基环树的数量开始，然后再来计算权值和。
由于放到一起统计的必须要有相同的权值和，于是它们的非叶节点数要相同。因此我们不妨设点集 $V$ 和叶节点集 $L$ 都相同，这样就可以放到一起统计了。故我们把 $V$ 和 $L$ 作为两维状态，用 $f_{V, L}$ 表示点集为 $V$，叶节点集为 $L$ 的基环树个数。
这样答案就等于 $\displaystyle \sum_{A \subseteq V} \sum_{L \subseteq A} f_{A, L} 2^{|A| - |L|}$。
但是如何取计算 $f_{V, L}$ 呢？
首先能够注意到，如果 $L = \varnothing$，即一个基环树 $B$ 没有叶节点，可以推知 $B$ 就是一个环。而我们刚才已经求得 (对于一个点集) 环的个数，因此有 $f_{V, \varnothing} = \mathrm{cycle}(V)$，其中 $\mathrm{cycle}(V)$ 即为由 $V$ 中的点构成的环的数量。
再令 $T_V$ 表示点集为 $V$ 的基环树个数。我们考虑如何转移 $f_{V, L}$ ($L \neq \varnothing$)
由于 $L$ 中的点一定是叶节点，因此它们一定唯一地连向 $V \setminus L$ 中的一个节点。
而这个方案数由乘法原理，等于 $L$ 中每个点 $v$ 连向集合 $V \setminus L$ 的方案数 $\mathrm{cross} \left( v, V \setminus L \right)$，是比较好求得的。
因此，把基环树中的这些叶节点 ($L$ 中的点) 去掉，就得到了它的一个子基环树。但是，在这个子基环树中，有些点可能又变回了叶节点，但也有可能没变会叶节点，再加上有些点可能本来就是叶节点。于是，这个数和 $T_V$ 的关系并不好处理。这给我们的 DP 带来了致命的阻碍。
那怎么办呢？看起来并没有什么好的办法处理。因此，像这道题一样，我们需要改变状态。
如果我们令 $F_{V, L}$ 表示点集为 $V$，其中 $L$ 中的点一定是叶节点，$V \setminus L$ 中的点可能是叶节点，这样的基环树的个数。
也就是说，令 $$ F_{V, L} = \sum_{L \subseteq I} f_{V, I} $$
由容斥原理 (或快速 Möbius 逆变换)，可以得到 $f_{V, L}$ 关于 $F_{V, L}$ 的表达式：
$$ f_{V, L} = \sum_{L \subseteq I} (-1)^{|I| - |L|} F_{V, I} \tag 1 \label 1 $$
于是，我们的目标从转移 $f$ 变成了转移 $F$。
首先，由于 $L$ 中的点一定是叶节点，因此这里的方案数还是 $\displaystyle \prod_{v \in L} \mathrm{cross} \left( v, V \setminus L \right)$。
接下来，我们还是要把 $L$ 中的点去掉。现在就好办了，这样得到的剩下的基环树，就恰好是点集是 $V \setminus L$ 的所有基环树，于是，我们就得到了转移方程：
$$ F_{V, L} = T_{V \setminus L} \cdot \prod_{v \in L} \mathrm{cross} \left( v, V \setminus L \right) \tag 2 \label 2 $$
注意到这个方程并不是完备的，因为当 $L = \varnothing$ 时，$F_{V, L}$ 和 $T_V$ 之间存在循环转移 (事实上它是一个恒等式)。
但是，我们注意到等式 $f_{V, \varnothing} = \mathrm{cycle}(V)$ 还没用过呢，将其代入 $\eqref 1$ 式，即可得到
$$ \mathrm{cycle}(V) = \sum_{I \subseteq V} (-1)^{|I|} F_{V, I} $$
将 $F_{V, \varnothing}$ 提到左边，即可得到
$$ F_{V, \varnothing} = \mathrm{cycle}(V) - \sum_{I \subseteq V; I \neq \varnothing} (-1)^{|I|} F_{V, I} \tag 3 \label 3 $$
由 $\eqref 2, \eqref 3$ 式，就可以作一个完整的转移了。
注意到 $T_V = F_{V, \varnothing}$，因此我们考虑直接转移 $T_V$。
将 $\eqref 2$ 代入 $\eqref 3$，得到
$$ T_V = \mathrm{cycle}(V) - \sum_{I \subseteq V; I \neq \varnothing} (-1)^{|I|} T_{V \setminus I} \cdot \mathrm{Cross} \left( I, V \setminus I \right) $$
可知复杂度是 $O \left( 3^n \right)$ 的 (枚举子集)。
但这里还有一个遗留问题，就是 $\displaystyle \mathrm{Cross} \left( I, V \setminus I \right) = \prod_{v \in I} \mathrm{cross} \left( v, V \setminus I \right)$ 该如何处理，这决定了我们该使用填表法还是刷表法。
观察等式右边的乘积式，我们发现，当 $V \setminus I$ 固定时，这个 $\mathrm{Cross}$ 值就非常有利于我们递推，因为可以对所有的点 $v \notin V \setminus I$，计算出 $\mathrm{cross} \left( v, V \setminus I \right)$ 的值。
所以说，在这道题中，我们应该使用刷表法！枚举 $V \setminus I$，去更新对应的 $T_V$！
这里面更新的具体过程在这里就略去了，还是比较好写的。可以在 $O \left( 3^n \right)$ 的时间内完成。
别忘了，到这里我们的问题还没结束呢，我们还需要来计算答案啊！
注意到我们得到的是 $F_{V, L}$ 而不是 $f_{V, L}$。如果我们此时暴力快速 Möbius 逆变换的话，时间复杂度就会升到 $O \left( 3^n \cdot n \right)$，很可能超时，因此我们需要对答案的式子进行化简。
将 $\eqref 1$ 式和 $\eqref 2$ 式分别代入，可得
$$ \sum_{A \subseteq V} \sum_{L \subseteq A} f_{A, L} \cdot 2^{|A| - |L|} = \sum_{A \subseteq V} \sum_{L \subseteq A} 2^{|A| - |L|} \sum_{L \subseteq I \subseteq A} (-1)^{|I| - |L|} F_{A, I} = \sum_{A \subseteq V} \sum_{L \subseteq A} 2^{|A| - |L|} \sum_{L \subseteq I \subseteq A} (-1)^{|I| - |L|} \cdot T_{A \setminus I} \cdot \mathrm{Cross} \left( I, A \setminus I \right) $$
将枚举 $I$ 放入最外层，得
$$ \sum_{I \subseteq V} 2^{|A| - |I|} \cdot T_{A \setminus I} \cdot \mathrm{Cross} \left( I, A \setminus I \right) \cdot \sum_{L \subseteq I} (-2)^{|I| - |L|} = \sum_{I \subseteq V} 2^{|A| - |I|} \cdot T_{A \setminus I} \cdot \mathrm{Cross} \left( I, A \setminus I \right) \cdot (-1)^{|I|} $$
注意这里还是涉及到量 $\mathrm{A \setminus I}$，故可以通过枚举 $A \setminus I$ 计算答案，我们可以在转移、计算 $\mathrm{Cross} \left( I, A \setminus I \right)$ 的时候顺便更新答案。
当然，最后不要忘记 $I = \varnothing$ 时的情况，因为这里没有限制 $I \neq \varnothing$。
总时间复杂度 $O \left( 3^n \right)$。
#include <bits/stdc++.h>
#define N 20
#define N2 65560
#define popc __builtin_popcount
#define parity __builtin_parity
#define ctz __builtin_ctz
typedef long long ll;
const int mod = 998244353, half_mod = 499122177;
int V, E, ALL;
int G[N][N];
int f[N2][N], cyc[N2], fy[N];
int cross[N2];
inline void add(int &x, const int y) {x = (x + y >= mod ? x + y - mod : x + y);}
int main() {
int i, j, k, u, v, c, tot; ll cur, ans = 0;
scanf("%d%d", &V, &E);
for (i = 1; i <= E; ++i)
scanf("%d%d", &u, &v), --u, --v, G[u][v] = G[v][u] = 1;
for (i = 0; i < V; ++i) f[1 << i][i] = 1;
ALL = ~(-1 << V); *cross = 1;
for (i = 1; i <= ALL; ++i) {
u = ctz(i); c = popc(i); tot = 0;
for (v = 0; v < V; ++v)
if (f[i][v]) {
if (G[u][v] && c > 2) add(tot, f[i][v]);
for (j = u + 1; j < V; ++j)
if (!(i >> j & 1) && G[v][j])
add(f[i | 1 << j][j], f[i][v]);
}
tot = (tot >> 1) + (-(tot & 1) & half_mod);
add(cyc[i], tot); ans += (ll)cyc[i] << c;
for (u = 0; u < V; ++u)
if (!(i >> u & 1))
for (fy[u] = v = 0; v < V; ++v)
fy[u] += (i >> v & 1) && G[u][v];
for (j = (i + 1) | i; j <= ALL; j = (j + 1) | i) {
u = ctz(k = j - i);
cross[k] = (ll)cross[k ^ 1 << u] * fy[u] % mod;
cur = (ll)(parity(k) ? cyc[i] : mod - cyc[i]) * cross[k] % mod;
add(cyc[j], (int)cur);
ans -= cur << c;
}
}
printf("%lld\n", ans % mod + (ans >> 63 & mod));
return 0;
}
坑1：在更新 ans 移位时不要忘记先将操作数转 long long。