HS
AFO
CF908H New Year and Boolean Bridges

# 题目描述

Your friend has a hidden directed graph with $n$ nodes. Let $f(u,v)$ be true if there is a directed path from node $u$ to node $v$ , and false otherwise. For each pair of distinct nodes, $u,v$ , you know at least one of the three statements is true:
1.$f(u,v) \ And \ f(v,u)$
2.$f(u,v) \ OR \ f(v,u)$
3.$f(u,v) \ XOR \ f(v,u)$
Here AND, OR and XOR mean AND, OR and exclusive OR operations, respectively. You are given an $n$ by $n$ matrix saying which one of the three statements holds for each pair of vertices. The entry in the $u$ -th row and $v$ -th column has a single character. 1. If the first statement holds, this is represented by the character ‘A’. 2. If the second holds, this is represented by the character ‘O’. 3. If the third holds, this is represented by the character ‘X’. 4. The diagonal of this matrix will only contain the character ‘-‘. Note that it is possible that a pair of nodes may satisfy multiple statements, in which case, the character given will represent one of the true statements for that pair. This matrix is also guaranteed to be symmetric. You would like to know if there is a directed graph that is consistent with this matrix. If it is impossible, print the integer -1. Otherwise, print the minimum number of edges that could be consistent with this information.

# 输入格式

The first line will contain an integer $n$ ( $1<=n<=47$ ), the number of nodes. The next $n$ lines will contain $n$ characters each: the matrix of what you know about the graph connectivity in the format described in the statement.

# 输出格式

Print the minimum number of edges that is consistent with the given information, or -1 if it is impossible.

# 输入输出样例

## 输入 #1

4
-AAA
A-AA
AA-A
AAA-


## 输出 #1

4


## 输入 #2

3
-XX
X-X
XX-


## 输出 #2

2


## 说明/提示

Sample 1: The hidden graph is a strongly connected graph. We can put all four nodes in a cycle.
Sample 2: One valid graph is $3→1→2$ . For each distinct pair, exactly one of $f(u,v),f(v,u)$ holds.

# 分析

$$g_{i,j}= \sum_k g_{i-1,k} \times f_{j \oplus k}$$

$$g_{i,j}= \sum_{a,b} [a|b==j] g_{i-1,a} \times f_{b}$$

# 一些对我而言的坑

• 第一次做子集变换时不全是$0/1$，所以直接异或1是错的。

# 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 50
#define maxl 8400000
{
register T sum=0;
register char cc=getchar();
int sym=1;
while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
if(cc=='-')sym=-1,cc=getchar();
sum=sum*10+cc-'0';
cc=getchar();
while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
return sym*sum;
}
template <typename T>inline T read(T &a)
{
return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
}
int n,cnt,a[maxl],f[maxl],g[maxl],fa[maxn],siz[maxn],idx[maxn];
char mp[maxn][maxn];
void FWT(int *A,int len)
{
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=j;k<j+i;k++)
f[k+i]+=f[k];
}
void init(int len)
{
for(int i=0;i<len;i++)
a[i]=1;
for(int i=1;i<len;i<<=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=j;k<j+i;k++)
a[k]*=-1;
}
int find(int x)
{
return fa[x]==x? x:fa[x]=find(fa[x]);
}
int main()
{
for(int i=1;i<=n;i++)
{
scanf("%s",mp[i]+1);
fa[i]=i;
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(mp[i][j]=='A')
fa[find(i)]=find(j);
for(int i=1;i<=n;i++)
siz[find(i)]+=1;
for(int i=1;i<=n;i++)
if(find(i)==i&&siz[i]>1)
idx[i]=1<<(cnt++);
if(!cnt)
{
printf("%d\n",n-1);
return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(mp[i][j]=='X')
{
int x=find(i),y=find(j);
if(x==y)
{
puts("-1");
return 0;
}
else if(idx[x]&&idx[y])
f[idx[x]|idx[y]]=true;
}
int len=1<<cnt;
FWT(f,len);
init(len);
for(int i=0;i<len;i++)
{
f[i]=!f[i];
g[i]=1;
}
FWT(f,len);
for(int i=0;i<cnt;i++)
{
int res=0;
for(int j=0;j<len;j++)
{
g[j]*=f[j];
res+=a[j]*g[j];
}
if(res)
{
printf("%d\n",n+i);
return 0;
}
}
return 0;
}



### 推荐文章

HS的博客

CF908H New Year and Boolean Bridges
FWT优化状压DP

2020-01-10