526互联

AtCoder Beginner Contest 220 H Security Camera

发布时间 2023-06-18 20:03:59作者: zltzlt

洛谷传送门

AtCoder 传送门

看到数据范围猜复杂度是 \(O(\text{poly}(n) 2^{\frac{n}{2}})\)，所以考虑折半。

至少有一个端点被选不好算，考虑转成两个端点都被选，但是边数奇偶性与 \(m\) 相同。

称编号 \(< \frac{n}{2}\) 的点为左点，编号 \(\ge \frac{n}{2}\) 的点为右点（点编号从 \(0\) 开始）

设 \(f_S\) 为只考虑左点，点集 \(S\) 的导出子图边数奇偶性，\(g_S\) 为只考虑右点，点集 \(S\) 的导出子图边数奇偶性，\(a_S\) 为右点中与左点点集 \(S\) 连边数量是奇数的点集，题目即求：

\[\sum\limits_{S, T} [f_S \oplus g_T \oplus (|a_S \cap T| \bmod 2) = m \bmod 2] \]

其中 \(|a_S \cup T| \bmod 2\) 是在求 \(S, T\) 之间边数的奇偶性。

考虑枚举 \(f_S = x, g_T = y\)，设 \(z = (m \bmod 2) \oplus x \oplus y\) 即 \(|a_S \cap T|\) 的奇偶性。那么就是要算：

\[\sum\limits_{S, T} ([f_S = x] \times [g_T = y] \times [|a_S \cap T| \bmod 2 = z] \]

考虑计算 \(h_P = \sum\limits_{S, T} [a_S \cap T = P] \times [f_S = x] \times [g_T = y]\)。设 \(b_P = \sum\limits_{S} [a_S = P] \times [f_S = x], c_P = [g_P = y]\)，那么：

\[h_P = \sum\limits_{S \cap T = P} b_S \times c_T \]

这样就化成了一个比较标准的按位与卷积形式，FWT 即可。

时间复杂度 \(O((n + m) 2^{\frac{n}{2}})\)，常数比较大。

code 
// Problem: H - Security Camera
// Contest: AtCoder - AtCoder Beginner Contest 220
// URL: https://atcoder.jp/contests/abc220/tasks/abc220_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 45;
const int maxm = (1 << 20) + 100;

int n, m, all, f[maxm], g[maxm], a[maxm], to[maxn];
ll ff[maxm], gg[maxm];
vector<int> vc[maxm];
pii e1[maxm], e2[maxm];

inline void FWT(ll *f, int x) {
	for (int k = 1; k < all; k <<= 1) {
		for (int i = 0; i < all; i += (k << 1)) {
			for (int j = 0; j < k; ++j) {
				f[i + j] += f[i + j + k] * x;
			}
		}
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	int m1 = 0, m2 = 0;
	for (int _ = 0, u, v; _ < m; ++_) {
		scanf("%d%d", &u, &v);
		--u;
		--v;
		if (u > v) {
			swap(u, v);
		}
		if (u < n / 2 && v >= n / 2) {
			to[v] |= (1 << u);
		} else if (u < n / 2 && v < n / 2) {
			e1[++m1] = make_pair(u, v);
		} else {
			e2[++m2] = make_pair(u, v);
		}
	}
	for (int S = 0; S < (1 << (n / 2)); ++S) {
		for (int i = 1; i <= m1; ++i) {
			int u = e1[i].fst, v = e1[i].scd;
			if ((S & (1 << u)) && (S & (1 << v))) {
				f[S] ^= 1;
			}
		}
	}
	for (int S = 0; S < (1 << (n - n / 2)); ++S) {
		for (int i = 1; i <= m2; ++i) {
			int u = e2[i].fst, v = e2[i].scd;
			if ((S & (1 << (u - n / 2))) && (S & (1 << (v - n / 2)))) {
				g[S] ^= 1;
			}
		}
	}
	for (int S = 0; S < (1 << (n / 2)); ++S) {
		for (int i = n / 2; i < n; ++i) {
			if (__builtin_parity(to[i] & S)) {
				a[S] |= (1 << (i - n / 2));
			}
		}
		vc[a[S]].pb(S);
	}
	all = (1 << (n - n / 2));
	ll ans = 0;
	for (int x = 0; x <= 1; ++x) {
		for (int y = 0; y <= 1; ++y) {
			for (int S = 0; S < all; ++S) {
				ff[S] = 0;
				for (int T : vc[S]) {
					ff[S] += (f[T] == x);
				}
				gg[S] = (g[S] == y);
			}
			FWT(ff, 1);
			FWT(gg, 1);
			for (int i = 0; i < all; ++i) {
				ff[i] *= gg[i];
			}
			FWT(ff, -1);
			for (int i = 0; i < all; ++i) {
				if ((__builtin_parity(i) ^ x ^ y) == (m & 1)) {
					ans += ff[i];
				}
			}
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}