题意
给定一个 \(N\) 个点 \(M\) 条边的简单无向联通图 \(G\)。每个边有红和蓝两种颜色，初始时每条边均是红色。
现在通过移除 \(G\) 中的一些边来获得一个新的无向图 \(G^{\prime}\)，求在所有的 \(2^M\) 种方案中有多少种方案可以使得 \(G^{\prime}\) 满足如下条件：
-
\(G^{\prime}\) 是联通图
-
通过采取如下操作可以使得所有的边变为蓝色：
- 选择一个点 \(u\)，将与 \(u\) 相邻的所有边变为蓝色
对 \(998244353\) 取模。
- \(1 \le N \le 17\)
- \(N - 1 \le M \le \frac{N\left(N - 1\right)}{2}\)
题解
首先我们可以发现，符合要求的子图 \(G^\prime\) 一定是二分图。
发现联通的要求很难满足，故考虑先计算不考虑联通限制下的答案。
设 \(g(S)\) 表示仅考虑与点集 \(S\) 相关的边，求使得图为二分图但不要求联通的方案数。
考虑对图进行黑白染色，通过枚举白色点集合 \(T\) 可以完成计算：
其中 \(\operatorname{count}_{S}\) 表示与点集 \(S\) 相关的边的数量。可以发现上式中的指数项即连接黑色点和白色点的边的数量。
\(\operatorname{count}_{S}\) 的值可以在通过对每个点集枚举所有边来实现，这里不多赘述。
下面考虑如何计算联通的方案数。
设 \(f(S)\) 表示仅考虑与点集 \(S\) 相关的边，求使得图为二分图且要求联通的方案数。
可以发现 \(f(S)\) 中包含的方案实际上是 \(g(S)\) 中去除了不联通的方案，因此可以考虑枚举出所有不联通的方案。
若不联通，那么图一定具有至少两个联通块，那么我们可以枚举 \(S\) 中编号最小的点所在的联通块，然后枚举该联通块中的点集 \(T\)，那么 \(S \setminus T\) 的连通性是没有限制。设 \(u = \min\limits_{x \in S} x\)，即点集 \(S\) 中的最小元素，那么有转移
时间复杂度 \(O(3^N + 2^NM)\)，空间复杂度 \(O(2^N + M)\)，可以通过。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
namespace MODINT {
constexpr valueType MOD = 998244353;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
constexpr valueType Inv2 = (MOD + 1) / 2;
}// namespace MODINT
using namespace MODINT;
bool check(valueType x, valueType k) {
return x & (1 << (k - 1));
}
valueType lowBit(valueType n) {
return n & -n;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M;
std::cin >> N >> M;
PairVector edges(M);
for (auto &iter : edges)
std::cin >> iter.first >> iter.second;
valueType const S = 1 << N;
ValueVector count(S, 0);
for (valueType s = 0; s < S; ++s) {
for (valueType i = 0; i < M; ++i) {
auto [u, v] = edges[i];
if (check(s, u) && check(s, v))
Inc(count[s], 1);
}
}
ValueVector G(S, 0), F(S, 0);
for (valueType s = 0; s < S; ++s) {
G[s] = 1;
for (valueType t = s; t > 0; t = (t - 1) & s)
Inc(G[s], pow(2, count[s] - count[t] - count[s ^ t]));
}
for (valueType s = 0; s < S; ++s) {
F[s] = G[s];
for (valueType t = s; t > 0; t = (t - 1) & s)
if (lowBit(t) < lowBit(s ^ t))
Dec(F[s], mul(F[t], G[s ^ t]));
}
std::cout << mul(F[S - 1], Inv2) << std::endl;
return 0;
}