题解
我们考虑计算 \(\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_{pos}\equiv \sum_{i=1\land i \ne pos}^{n-1} a_{n,i} x_i + a_{n,n} \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?
*/
- Universal Northern Stage Good Setsuniversal northern stage good universal stage 6555 good universal stage the 2nd universal qingdao stage the universal contest nanjing stage universal binjiang stage the universal okayama stage the universal shenyang stage the universal shaanxi stage 6735 universal stage hefei the