Codeforces

Luogu

分析

显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。

显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。

因为点数 $\geq 2$ 的强连通分量只有至多 $23$ 个，因此可以状压 DP。设 $dp_{i,S}$ 表示加 $i$ 条边能否把 $S$ 中的强连通分量合并，显然有转移
$$
dp_{i,S}=\bigvee_{S_1\cup S_2=S}dp_{i-1,S_1}\land dp_{0,S_2}
$$
求 $dp_{0,S}$ 比较简单，判断能否向 $S-\operatorname{lowbit}(S)$ 中加入 $\operatorname{lowbit}(S)$ 即可，可以预处理每个强连通分量和哪些强连通分量有 XOR 边来快速判断。

因为只要判断合法性，所以把 $\lor$ 写成 $\sum$、$\land$ 写成 $\times$ 也不影响，那么就是一个或卷积的形式了。我们只需要求出最小的满足 $dp_{i,U}\neq 0$ 的 $i$ 即可，答案即为 $n+i$。

然而每次暴力 FWT 转移是 $\mathcal{O}(n^22^{n/2})$ 的，不够优秀。注意到我们只要求 $dp_{i,U}$，所以可以预处理 IFWT 前每个位置对 IFWT 后 $U$ 这个位置的贡献，这样子就可以做到 $\mathcal{O}(n2^{n/2})$ 了。

这个东西有一个公式，可以看 memset0 的题解。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=47+10;

int n; char G[N][N];
int sz[N],id[N],E[N],tot=0;
int dp[1<<23],tr[1<<23],c[1<<23];

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int FWT(int* A,int n,int op) {
    for (int i=1;i<n;i<<=1)
        for (int j=0;j<n;j+=i<<1)
            for (int k=0;k<i;++k) A[i+j+k]+=op*A[j+k];
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) scanf("%s",G[i]+1);
    for (int i=1;i<=n;++i) f[i]=i;
    for (int i=1;i<=n;++i)
        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; }
    for (int i=1;i<=n;++i) ++sz[find(i)];
    for (int i=1;i<=n;++i) if (sz[i]>1) id[i]=++tot;
    if (!tot) { printf("%d\n",n-1); return 0; }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) {
            if (G[i][j]!='X') continue;
            int u=find(i),v=find(j);
            if (sz[u]>1&&sz[v]>1)
                E[id[u]]|=1<<(id[v]-1),E[id[v]]|=1<<(id[u]-1);
        }
    dp[0]=1;
    for (int S=0;S<1<<tot;++S) {
        int t=S&-S,T=S^t;
        if (!(E[__builtin_ctz(t)+1]&T)) dp[S]=dp[T];
    }
    if (dp[(1<<tot)-1]) { printf("%d\n",n); return 0; }
    FWT(dp,1<<tot,1); memcpy(tr,dp,sizeof(tr));
    for (int i=0;i<1<<tot;++i)
        c[i]=__builtin_popcount(i^((1<<tot)-1))&1?-1:1;
    int ans=n;
    while (1) {
        ++ans;
        for (int i=0;i<1<<tot;++i) dp[i]*=tr[i];
        int now=0;
        for (int i=0;i<1<<tot;++i) now+=dp[i]*c[i];
        if (now) break;
    }
    printf("%d\n",ans);
    return 0;
}