【Codeforces 908H】 New year and Boolean Bridges

发表于
http://codeforces.com/problemset/problem/908/H

题目链接

【Codeforces 908H】 New year and Boolean Bridges

做法

发现 $ f(u, v)~OR~f(v, u) $ 满足当且仅当 $ f(u, v)~AND~f(v, u) $ 和 $ f(u, v)~XOR~f(v, u) $ 满足，故 $ f(u, v)~OR~f(v, u) $ 不予考虑。
若 $ f(u, v)~AND~f(v, u) $ 满足，则 $ u, v $ 在同一联通块；若 $ f(u, v)~XOR~f(v, u) $ 满足，则 $ u, v $ 不在同一联通块，所以可能产生矛盾，需要判无解。
最后的图一定是个弱连通块，即至少有 $ n - 1 $ 条边，由于一个大小为 $ 1 $ 的独立点对答案贡献为 $ 1 $ ，所以我们要最小化大小 $ \geq 2 $ 的连通块数目，而这样的连通块数目最多有 $ m = \lfloor \frac{ n }{ 2 } \rfloor = 23 $ 个。
考虑状压。令 $ fb[i] $ 表示 $ i $ 号点不能与那些点作为一个强连通块， $ le[i] $ 表示选择状态为 $ i $ 的点作为一个强联通块的合法性，可以通过 $ lowbit $ 从 $ fb[i] $ 推出 $ le[i] $ 。
每新加入一条边，弱连通块合法性满足 $ F[i] = \sum_{ j | k = i }{ F’[j] \times le[k] } $ ， $ F’[j] $ 表示上一次操作的 $ F[j] $ 。
这样可以 $ FWT $ 优化，最多进行 $ m $ 次，时间复杂度 $ O(m^2 2^{m}) $ ，并不能过去。
考虑我们 $ FWT $ 后不需要 $ IFWT $ 回去，每次求单点系数。 $ FWT $ 的过程可以理解为一个行向量右乘一个矩阵得到新的行向量，这个矩阵就是我们想要的系数，可以证明：

mu[x][y] = (x & y) != x ? 0 : ksm(-1, popcount(ksm(x, y)); 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 50, M = 10000000;
char g[N][N];
int n, f[N], ans;
int sz[N], id[N], lg[M], len, cnt = 0, fb[N], le[M];
int nw[M], mu[M];

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return(int)((ll)x * y % mod); }
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void fwt(int *A, int lmt, int opt) {
	for(int mid = 1; mid < lmt; mid <<= 1)
		for(int j = 0; j < lmt; j += mid << 1)
			for(int k = 0; k < mid; k++) {
				if(opt == 1) A[j + mid + k] = add(A[j + mid + k], A[j + k]);
				else A[j + mid + k] = sub(A[j + mid + k], A[j + k]);
			}
}
int main() {
	scanf("%d", &n); for(int i = 1; i <= n; i++) f[i] = i;
	for(int i = 1; i <= n; i++) {
		scanf("%s", g[i] + 1);
		for(int j = 1; j <= n; j++) if(g[i][j] == 'A') f[find(i)] = find(j);
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(g[i][j] == 'X' && find(i) == find(j)) { puts("-1"); return 0; }
	ans = n - 1;
	for(int i = 1; i <= n; i++) ++sz[find(i)];
	for(int i = 1; i <= n; i++)
		if(find(i) == i && sz[i] > 1) id[i] = cnt, lg[1 << cnt] = cnt, ++cnt;
	if(!cnt) { printf("%d\n", ans); return 0; }
	len = (1 << cnt);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
			if(g[i][j] != 'X') continue;
			if(sz[find(i)] > 1 && sz[find(j)] > 1) {
				fb[id[find(i)]] |= (1 << id[find(j)]);
				fb[id[find(j)]] |= (1 << id[find(i)]);
			}
		}
	le[0] = 1; for(int i = 0; i < cnt; i++) le[1 << i] = 1;
	for(int i = 0; i < len; i++) {
		if(le[i]) continue;
		int x = lg[i & -i], y = i - (1 << x);
		if(le[y] && (fb[x] & y) == 0) le[i] = 1;
	}
	fwt(le, len, 1);
	mu[0] = (cnt & 1) ? -1 : 1;
	for(int i = 1; i < len; i++) mu[i] = sub(0, mu[i ^ (i & -i)]);
	for(int i = 0; i < len; i++) nw[i] = le[i];
	for(int i = 1;; i++) {
		int z = 0;
		for(int j = 0; j < len; j++) z = add(z, mul(mu[j], nw[j]));
		if(z) { printf("%d\n", ans + i); break; }
		for(int j = 0; j < len; j++) nw[j] = mul(nw[j], le[j]);
	}
	return 0;
}