题解
我们考虑计算 \(\sum_{S\subseteq\{1,2,3,\cdots,n\}} (-1)^{cnt(S)}\)，这里 \(cnt(S)\) 表示 \(S\) 集合的导出子图的边数。
我们记 \(x_i=[i\in S]\)。
我们考虑删掉 \(n\) 号点。
注意到如果 \(x_i\) 的取值会影响 \(cnt(s)\) 的奇偶性，则正负相消，贡献为 \(0\)。
所以我们需要保证下列条件满足：
\[\sum_{i=1}^{n-1}a_{n,i} x_i + a_{n,n}\equiv 0\pmod 2 \]我们考虑是否存在位置 \(pos\)，满足 \(a_{n,pos}(pos\ne n) =1\)。
-
如果不存在这样的 \(pos\)，那我们根据 \(a_{n,n}\) 的取值分类讨论：
- \(a_{n,n}=0\)，则贡献乘 \(2\)；
- \(a_{n,n}=1\)，贡献变成 \(0\)。
-
如果存在一个位置 \(pos\)，满足 \(a_{n,pos}=1\)。
那么，根据 \(\sum_{i=1}^{n-1}a_{n,i} x_i + a_{n,n}\equiv 0\pmod 2\)，我们可以得出：
我们考虑对于一个序列 \(x_1,x_2,\cdots,x_n\) 计算答案。
\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=i+1}^n a_{i,j} x_i x_j\\ \equiv&\sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1} a_{i,j} x_i x_j\\ \equiv&\sum_{i=1\land i \ne pos}^{n - 1}\sum_{j=i+1\land j\ne pos}^{n - 1} a_{i,j} x_ix_j+\sum_{i=1\land i \ne pos}^{n-1} a_{i,pos} x_ix_{pos} + a_{pos,pos}x_{pos}\\ \equiv&\sum_{i=1\land i \ne pos}^{n - 1}\sum_{j=i+1\land j\ne pos}^{n - 1} a_{i,j} x_i x_j+\sum_{i=1\land i \ne pos}^{n-1} a_{i,pos} x_i(\sum_{i=1\land i \ne pos}^{n-1} a_{n,i} x_i+a_{n,n})+a_{pos,pos}(\sum_{i=1\land i \ne pos}^{n-1} a_{n,i} x_i+a_{n,n}) \end{aligned} \] 于是，我们就可以把 \(n\times n\) 的矩阵，在 \(O(\frac{n^2}{w})\) 的时间内，变成 \((n-2)\times (n-2)\) 的矩阵。
注意到 \(x_n\) 有两种取值，所以贡献要 \(\times 2\)。注意到上述式子继续展开，则 \(a_{pos,pos}a_{n,n}\) 的项，所以贡献可能 \(\times (-1)\)。
总时间复杂度 \(O(\frac{n^3}{w})\)。
代码
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 1010, MOD = 998244353, inv2 = (MOD + 1) >> 1;
int n, m, ans = 1, t = 1;
bitset <N> a[N];
signed main() {
read(n), read(m);
F(i, 1, n) t = 2 * t % MOD;
F(i, 1, m) {
int x, y; read(x), read(y);
a[x][y] = a[y][x] = true;
}
DF(i, n, 1) {
bool flag = false;
F(j, 1, i - 1) flag |= a[i][j];
if (flag) {
int pos = -1;
F(j, 1, i - 1)
if (a[j][i]) {
pos = j;
break;
}
assert(~pos);
a[i][pos] = false;
F(j, 1, i - 1) if (j != pos && a[pos][j]) {
a[j] ^= a[i];
if (a[i][i] ^ a[i][j]) a[j][j].flip();
}
F(j, 1, i - 1) if (j != pos && a[i][j]) {
a[j] ^= a[pos];
}
if (a[pos][pos]) {
F(j, 1, i - 1)
if (j != pos && a[i][j]) a[j][j].flip();
if (a[i][i]) ans = (ll) ans * (MOD - 1) % MOD;
}
F(j, 1, i - 2) {
if (j >= pos) a[j] = a[j + 1];
bitset <N> s = (a[j] >> pos);
a[j] = a[j] ^ (s << pos) ^ ((s >> 1) << pos);
}
i--;
ans = (ll) ans * 2 % MOD;
} else if (!a[i][i]) ans = (ll) ans * 2 % MOD;
else ans = 0;
}
cout << (ll) (t + ans) * inv2 % MOD;
return 0;
}
/* why?
*/