CF908H 题解

· · 题解

首先可以根据 \text{AND} 边建出图中必定存在的强连通子图。

然后发现显然的无解情况是对于在同一个强连通分量里的两个点，他们两个之间存在 \text{XOR} 边，而其他情况下必定有解，接下来考虑构造。

首先原图任意点对都是弱联通的，所以如果我们已经确定了图中所有的极大强连通分量，那么边数最少的方案就是把他们随便连成一条链，同时这种构造必定合法。

考虑每个极大强连通分量，如果他的大小 \text{size}>1，那么他内部至少需要 \text{size} 条边，否则需要 0 条。

容易发现在根据 \text{AND} 边建出的强连通分量之间连边只会使全局由合法变成不合法，而不会使不合法变成合法，同时把一个大小为 1 的极大强连通分量和另外的并起来不会对最终的边数造成任何影响，所以可以把所有的大小为 1 的扔掉。

现在我们只有大小超过 1 的极大强连通分量，不难发现每次合并两个分量造成的唯一影响只有使缩完点后链的长度减 1，也即全局所需边数减 1。

那么目标就是求出在合法的情况下，最少剩下几个强连通分量。

我们把强连通分量之间根据给出的 \text{XOR} 关系连边，发现终态下的每个强连通分量必定对应一个独立集，而初始大小超过 1 的强连通分量个数只有 \lfloor\frac{n}{2}\rfloor，于是启发我们先暴力找出所有的独立集，然后直接进行若干次子集卷积，当卷出来的数组中代表全集的下标处的值非零，就找到了所需要的强连通分量的最少个数，复杂度 O(2^{\lfloor\frac{n}{2}\rfloor}n^3)。

但是发现这里的子集卷积可以直接替换成或卷积，正确性显然。同时发现求的只是单个下标处的值，所以直接每次使用 FWT 数组点积乘即可，同时不需要 iFWT 回去，只需要求出每个下标对全集下标的贡献系数然后反演一遍即可，复杂度 O(2^{\lfloor\frac{n}{2}\rfloor}n)。

#include "bits/stdc++.h"
#define f(i ,m ,n ,x) for (int i = (m) ,i##END = (n) ; i <= i##END ; i += (x))

const int N = 55 ;
int n ,fa[N] ,siz[N] ,a[1 << 24] ,b[1 << 24] ,v[1 << 24] ; char ch[N][N] ; bool lnk[N][N] ;
std :: vector < int > scc[N] ;

int main (void) {
    std :: ios :: sync_with_stdio (false) ,
    std :: cin.tie (nullptr) ,std :: cout.tie (nullptr) ;

    std :: cin >> n ; f (i ,1 ,n ,1) 
        std :: cin >> (ch[i] + 1) ,fa[i] = i ,siz[i] = 1 ;

    auto Find = [] (auto &&self ,int x) -> int 
    { return x == fa[x] ? x : fa[x] = self (self ,fa[x]) ;} ;

    f (i ,1 ,n - 1 ,1) f (j ,i + 1 ,n ,1) if (ch[i][j] == 'A') {
        int u = Find (Find ,i) ,v = Find (Find ,j) ;
        if (u == v) continue ;
        else fa[u] = v ,siz[v] += siz[u] ;
    }

    f (i ,1 ,n - 1 ,1) f (j ,i + 1 ,n ,1) if (ch[i][j] == 'X') 
        if (Find (Find ,i) == Find (Find ,j)) return std :: cout << "-1\n" ,0 ;

    int Single = 0 ; f (i ,1 ,n ,1)
        Single += (Find (Find ,i) == i) && (siz[i] == 1) ; 

    int cnt = 0 ; f (i ,1 ,n ,1) if (Find (Find ,i) == i) if (siz[i] != 1) 
    { cnt++ ; f (j ,1 ,n ,1) if (Find (Find ,j) == i) scc[cnt].emplace_back (j) ;}

    if (!cnt) return std :: cout << Single - 1 << '\n' ,0 ;
    if (cnt == 1) return std :: cout << n << '\n' ,0 ;

    f (i ,1 ,cnt - 1 ,1) f (j ,i + 1 ,cnt ,1)
        for (auto x : scc[i]) for (auto y : scc[j])
            if (ch[x][y] == 'X') lnk[i][j] = lnk[j][i] = true ;

    a[0] = 1 ; f (i ,1 ,cnt ,1) a[1 << i - 1] = 1 ;
    f (j ,3 ,(1 << cnt) - 1 ,1) if (__builtin_popcount (j) > 1) {
        int lbt = j & (-j) ,num = std :: __lg (lbt) + 1 ; if (a[j ^ lbt]) {
            f (i ,1 ,cnt ,1) if (((j ^ lbt) >> i - 1) & 1)
                if (lnk[i][num]) goto her ;
            a[j] = 1 ; her : ;
        }
    }

    [&] (int *a) -> void {
        for (int len = 2 ,mid = 1 ; len <= 1 << cnt ; mid = len ,len <<= 1) 
            f (i ,0 ,(1 << cnt) - 1 ,len) f (j ,0 ,mid - 1 ,1) a[i + j + mid] += a[i + j] ;
    } (a) ;

    f (i ,0 ,(1 << cnt) - 1 ,1)
        v[i] = cnt - __builtin_popcount (i) & 1 ? -1 : 1 ;

    f (i ,0 ,(1 << cnt) - 1 ,1) b[i] = 1 ;
    int tot = 0 ; while (true) {
        tot++ ; 
        f (i ,0 ,(1 << cnt) - 1 ,1) b[i] *= a[i] ;
        int res = 0 ; f (i ,0 ,(1 << cnt) - 1 ,1) res += v[i] * b[i] ;
        if (res) return std :: cout << tot - 1 + n << '\n' ,0 ;
    }
    return 0 ;
}