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 ;
}