【CodeForces908H】New Year and Boolean Bridges （FWT）

The main idea of the topic

For a directed graph $(1\le n\le 47)$, Definition $f(u,v)$ The value of is true, If and only if there is a path that makes $u$ Can walk to $v$
Give me a “ Adjacency matrix ”$A[i][j]$：
If A[i][j]=='A', be f(u,v) and f(v,u) by true
If A[i][j]=='X', be f(u,v) xor f(v,u) by true
If A[i][j]=='O', be f(u,v) or f(v,u) by true
（ Keep the matrix symmetric ）

To construct a directed graph , Satisfy adjacency matrix A, At least how many edges are needed .

Answer key

First of all, we can know that the whole picture must be connected （ Neither of the above conditions says that the two points are completely disconnected ）
then , If A[i][j]=='A', be $i$ And $j$ It must be in a strongly connected block , First, all strongly connected blocks are treated with the union search set .
One point is size(size>=2) Strongly connected block of , need size This strongly connected block is connected by two edges （ A ring ）. Let's have a total of m A strong connection block , Then you need m-1 Edges connect connected blocks into a tree .

And after collecting and processing , Some strongly connected blocks can be merged .
obviously , The fewer connected blocks the better （ Merge once , One less tree edge ）, however , There is xor Strongly connected blocks of a relation cannot be merged .
siz>=2 Has the most strongly connected blocks 23 individual , Use shape pressure to express ,$g_k[S]$ Signify a company k Tree edge , The set is S Whether the connected blocks of can be connected .
Preprocess first $f[S]=g_0[S]$, About to exist in the collection xor The two connected blocks of the relationship are marked as 0, The rest are 1
set up T by S Subset , Transfer
$$g_{k+1}[S]||=g_k[T]\&\&g_k[SxorT]$$
In fact, such transfer can also （S And T No restrictions ）
$$g_{k+1}[SorT]+=g_k[S]\times g_k[T]$$
Exactly or convolution , You can use FWT do
So we can go from $g_0$ Start , Keep rolling $f$, until $g_k[all]$ Not for 0, You need to k Tree edge .
In order to simplify the , On each roll $f$ after , Don't go back FWT Back again , Each position pair can be calculated in advance all The contribution of , Only calculate all It's just a factor of

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=50,MAXS=(1<<24)+10;

int n;
char adj[MAXN][MAXN];

int fa[MAXN],siz[MAXN];
int Root(int u)
{
    
    if(fa[u]==0)
        return u;
    return fa[u]=Root(fa[u]);
}
void Union(int u,int v)
{
    
    int r1=Root(u),r2=Root(v);
    if(r1==r2)
        return;
    fa[r1]=r2;
    siz[r2]+=siz[r1];
}

void FWT(int A[],int n)
{
    
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int l=j,r=j+i;l<i+j;l++,r++)
                A[r]+=A[l];
}

int m,id[MAXN];
int f[MAXS],g[MAXS],a[MAXS];

int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",adj[i]+1);

    for(int i=1;i<=n;i++)
        siz[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(adj[i][j]=='A')
                Union(i,j);

    int ans=0;

    for(int i=1;i<=n;i++)
    {
    
        int r=Root(i);
        if(r==i)
        {
    
            if(siz[r]>=2)
                id[r]=++m;
            ans+=siz[r];
        }
    }

    if(m==0)
    {
    
        printf("%d\n",n-1);
        return 0;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(adj[i][j]=='X')
            {
    
                int r1=Root(i),r2=Root(j);
                if(r1==r2)
                {
    
                    puts("-1");
                    return 0;
                }
                if(id[r1]&&id[r2])
                    f[(1<<(id[r1]-1))|(1<<(id[r2]-1))]=1;
            }
    for(int s=1;s<(1<<m);s++)
        for(int i=1;i<=n;i++)
            if(s&(1<<(i-1)))
                f[s]|=f[s^(1<<(i-1))];
    for(int s=0;s<(1<<m);s++)
        f[s]=f[s]^1;

    FWT(f,1<<m);

    for(int i=0;i<(1<<m);i++)
        a[i]=1;
    for(int i=1;i<(1<<m);i<<=1)
        for(int j=0;j<(1<<m);j+=(i<<1))
            for(int l=j;l<i+j;l++)
                a[l]*=-1;

    for(int i=0;i<(1<<m);i++)
        g[i]=1;
    for(int i=1;;i++)
    {
    
        int tmp=0;
        for(int j=0;j<(1<<m);j++)
            g[j]*=f[j];
        for(int j=0;j<(1<<m);j++)
            tmp+=g[j]*a[j];
        if(tmp)
        {
    
            printf("%d\n",ans+i-1);
            return 0;
        }
    }

    return 0;
}