题目链接
做法
发现 $ 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));
#includeusing 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;}