Codeforces908H. New Year and Boolean Bridges【并查集+强联通+FWT】

题目大意：

有一个n个点的有向图。

定义i能到达j时f(i,j)=1，否则f(i,j)=0。

对于每个点对(i,j)，给定以下三个条件中的某一个为真：

(1) f(i,j) and f(j,i)=1；

(2) f(i,j) or f(j,i)=1；

(3) f(i,j) xor f(j,i)=1。

求满足条件时的最小边数。

1<=n<=47。

解题思路：

等价于满足以下两个条件：

(1)满足 and a n d 的点对一定在同一个强连通分量里。

(2)一个强连通分量里不能有 xor x o r ，否则无解。

将满足 and a n d 的点对用并查集连起来当做一个块。

一些块能合并成一个块当且仅当它们之间没有 xor x o r 。

大小为 1 1 的块要跟外面连通显然贡献是 11，对于 size≥2 s i z e ≥ 2 的块，最优肯定是用 size s i z e 条边连一个环，而所有块还要连成一棵树，所以最后就是最小化 ≥2 ≥ 2 的块数 cnt c n t ，答案就是 n+cnt−1 n + c n t − 1 。

注意 ≥2 ≥ 2 的下等于 n/2 n / 2 ，可以用状压了，一下 m m 表示初始时 ≥2≥2 的块数。

先dp预处理出每个集合能否合并，将不合法点对的值设为 1 1 ，那么求子集和，为0即可合并，否则不行。暴力求子集和是O(3m)O(3m)的，但其实子集并卷积FWT时就是求子集和，所以是 O(m2m) O ( m 2 m ) 的。

暴力就是枚举子集。

令 f(i) f ( i ) 表示 i i 代表的块合并后的最小块数。

f(i)=min{f(j)+f(i⊕j)}(j⊂i)f(i)=min{f(j)+f(i⊕j)}(j⊂i)

时间复杂度 O(3m) O ( 3 m )

令 f(i) f ( i ) 有值当且仅当 i i 代表的块能合并成一块。

好比邻接矩阵的 kk 次方对应两点间是否有长度为 k k 的路径，我们需要找到最小的 kk 使得 k k 个 ff 进行集合并卷积后 f(2m−1) f ( 2 m − 1 ) 有值，那么 cnt=k c n t = k 。

(开始认为应该是子集卷积，后来发现集合并卷积也没错)

一个直观想法是每次做FWT-UFWT后检查，但最坏会做 m−1 m − 1 次，不太能过。

其实可以模拟UFWT的过程处理出每个位置的点值对 f(2m−1) f ( 2 m − 1 ) 的系数，先将 f f FWT，每次点乘后不用再UFWT回去，而是直接O(2m)O(2m)算出 f(2m−1) f ( 2 m − 1 ) 即可。

复杂度为 O(n2n/2) O ( n 2 n / 2 )

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
const int M=;
int n,m,fmp[N],s[N],idx[N],f[M],g[M],a[M];
char mp[N][N];
int F(int x){return fmp[x]==x?x:fmp[x]=F(fmp[x]);}
void FWT(int a[],int len)
{
    for(int i=;i<len;i<<=)
        for(int j=;j<len;j+=(i<<))
            for(int k=j;k<j+i;k++)
                f[k+i]+=f[k];
}
void init(int len)
{
    for(int i=;i<len;i++)a[i]=;
    for(int i=;i<len;i<<=)
        for(int j=;j<len;j+=(i<<))
            for(int k=j;k<j+i;k++)
                a[k]*=-;       
}
int main()
{
    //freopen("lx.in","r",stdin);
    scanf("%d",&n);
    for(int i=;i<n;i++)scanf("%s",mp[i]),fmp[i]=i;
    for(int i=;i<n;i++)
        for(int j=;j<i;j++)
            if(mp[i][j]=='A')fmp[F(i)]=F(j);
    for(int i=;i<n;i++)++s[F(i)];
    for(int i=;i<n;i++)if(F(i)==i&&s[i]>)idx[i]=<<m++;
    if(!m){cout<<n-<<'\n';return ;}
    for(int i=;i<n;i++)
        for(int j=;j<i;j++)
            if(mp[i][j]=='X')
            {
                if(F(i)==F(j)){puts("-1");return ;}
                else if(idx[F(i)]&&idx[F(j)])f[idx[F(i)]|idx[F(j)]]=;
            }
    int len=<<m;FWT(f,len);
    for(int i=;i<len;i++)f[i]=!f[i],g[i]=;
    FWT(f,len),init(len);
    for(int i=;i<m;i++)
    {
        int cur=;
        for(int j=;j<len;j++)g[j]*=f[j],cur+=a[j]*g[j];
        if(cur){cout<<n+i<<'\n';return ;}
    }
    return ;
}