题意：就是判断a数组是否存在，满足b数组的关系。
思路：把每个数有31位，每位上不是1就是0，所以就是SAT问题，刚开始尝试将点拆成500*31*2，一直MLE，就按位判断，就是31次判断，每次1000个点，，
SAT建图：
关系 添加弧
(1)A and B = 0 A->!B , B->!A
(2)A and B = 1 !A->A , !B->B
(3)A or B = 0 A->!A , B->!B
(4)A or B = 1 !A->B , !B->A
(5)A xor B = 0 A->B , B->A , !A->!B , !B->!A
//(A == 1 && B == 0 : A -> B, !B -> !A; A == 0 && B == 1 : !A -> !B, B -> A;)
(6)A xor B = 1 A->!B , B->!A , !B->A , !A->B
#include<iostream>
#include<stdio.h>
#include<stack>
#include<string.h>
const int N=2000;
using namespace std;
int head[N],num,low[N],dfs[N],belong[N],idx,ans,n;
int b[510][510];
bool ins[N];
struct edge
{
int ed,next;
}e[N*1000];
void addedge(int x,int y)
{
e[num].ed=y;e[num].next=head[x];head[x]=num++;
}
void p1(int i,int j,int w)//并关系
{
if(w&1)//i&j=1
{
addedge(n+i,i);
addedge(n+j,j);
}
else//i&j=0
{
addedge(i,n+j);
addedge(j,n+i);
}
}
void p2(int i,int j,int w)//或关系
{
if(w&1)
{
addedge(i+n,j);
addedge(j+n,i);
}
else
{
addedge(i,i+n);
addedge(j,j+n);
}
}
void p3(int i,int j,int w)//异或关系
{
if(w&1)
{
addedge(i,j+n);
addedge(j,i+n);
addedge(i+n,j);
addedge(j+n,i);
}
else
{
addedge(i,j);
addedge(j,i);
addedge(i+n,j+n);
addedge(j+n,i+n);
}
}
stack<int>Q;
void Tarjan(int u)
{
int i,v;
low[u]=dfs[u]=idx++;
ins[u]=true;
Q.push(u);
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(dfs[v]==-1)
{
Tarjan(v);
low[u]=low[u]>low[v]?low[v]:low[u];
}
else if(ins[v])
low[u]=low[u]>dfs[v]?dfs[v]:low[u];
}
if(dfs[u]==low[u])
{
do
{
v=Q.top();
Q.pop();
ins[v]=false;
belong[v]=ans;
}while(v!=u);
ans++;
}
}
bool solve()
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(i&1&&j&1)//或
p2(i,j,b[i][j]);
else if(!(i&1)&&!(j&1))//并
p1(i,j,b[i][j]);
else//异或
p3(i,j,b[i][j]);
b[i][j]>>=1;
}
}
idx=1;ans=1;
memset(dfs,-1,sizeof(dfs));
memset(ins,false,sizeof(ins));
for(i=0;i<n+n;i++)
{
if(dfs[i]==-1)
Tarjan(i);
}
for(i=0;i<n;i++)
{
if(belong[i]==belong[i+n])break;
}
if(i<n)return false;
else return true;
}
bool judge()
{
for(int i=0;i<n;i++)
{
if(b[i][i]!=0)return true;
for(int j=i+1;j<n;j++)
if(b[i][j]!=b[j][i])return true;
}
return false;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=-1)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
}
if(judge())
{printf("NO\n");continue;}
for(i=0;i<31;i++)
{
memset(head,-1,sizeof(head));
num=0;
if(!solve())break;
}
if(i<31)printf("NO\n");
else printf("YES\n");
}
return 0;
}