https://codeforces.com/contest/2043/problem/E
首先,由于位运算的性质,我们分开每一位来看,如果有一位不能使得a与b对应元素相等,那就无解。其次,与运算作用只有置0,或预算作用只有置1。
对某一位,我们会发现某些“必须执行的操作”,如某一行必须执行一次置0,某一列必须执行一次置1。
同时,还可能出现某一行置0之后,该行某些元素实际上为1,那么就在这些元素的列上置1。那这些列上可能又有某些行需要置0的。所以这是个连锁反应。
非常好玩的一点,就是这里应该想到dfs、或拓扑排序。对“连锁反应”建图,然后检测一下存不存在环。如果有环就无解,否则就能通过某种顺序,使得该位上a的所有元素与b中的元素相等。
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,n,m) for(int (i)=(n);(i)<=(m);(i)++)
#define repd(i,n,m) for(int (i)=(n);(i)>=(m);(i)--)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
struct graph
{
int V;
vector<vector<int>> g;
vector<int> color;
bool dfs(int v)
{
if(color[v] == 2) return false;
if(color[v] == 1) return true;
color[v] = 1;
bool res = false;
for(auto x:g[v]){
if(color[x]==2) continue;
else if(color[x]==0){
res |= dfs(x);
}else res = true;
}
color[v] = 2;
return res;
}
void add_edge(int x, int y)
{
g[x].push_back(y);
}
graph(int V)
{
this->V = V;
this->g.resize(V);
this->color.resize(V);
};
};
int get_bit(int x, int y)
{
return (x >> y) & 1;
}
bool check(const vector<vector<int>>& a, const vector<vector<int>>& b, int k)
{
int n = a.size();
int m = a[0].size();
vector<bool> must_row(n);
vector<bool> must_col(m);
auto G = graph(n + m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(get_bit(a[i][j], k) != get_bit(b[i][j], k))
{
if(get_bit(b[i][j], k) == 0) must_row[i] = true;
else must_col[j] = true;
}
if(get_bit(b[i][j], k) == 0) G.add_edge(j + n, i);
else G.add_edge(i, j + n);
}
for(int i = 0; i < n; i++)
if(must_row[i] && G.dfs(i))
return false;
for(int j = 0; j < m; j++)
if(must_col[j] && G.dfs(j + n))
return false;
return true;
}
void solve(){
int n, m;
scanf("%d %d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
auto b = a;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d", &b[i][j]);
for(int i = 0; i < 30; i++)
{
if(!check(a, b, i))
{
puts("No");
return;
}
}
puts("Yes");
}
int main(){
ifstream test_file("0in.txt");
if (test_file) {
freopen("0in.txt", "r", stdin);
freopen("0output.txt", "w", stdout);
}
int T = 1;
#ifdef MULTI_TEST
cin>>T;
#endif
while(T--){
solve();
}
return 0;
}