【Codeforces 908H】 New year and Boolean Bridges

题目链接

【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));

#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;
}