[Easy-Medium] CF2043E Matrix Transformation

简要题意

给定两个 $n\times m$ 的矩阵 $A,B$，你可以进行任意次下列操作，使得 $A=B$：

1. 选定一行 $i$ 和一个自然数 $x$，将这一行每一个数按位与上 $x$。
2. 选定一列 $j$ 和一个自然数 $x$，将这一列每一个数按位或上 $x$。

输出是否存在有限次操作的方案。

$T$ 组数据。$1\leq T\leq 100,1\leq n\cdot m\leq 10^3,0\leq A_{ij},B_{ij}\leq 10^9$。

思路

首先由于位运算中位与位之间独立，所以可以将 $A,B$ 拆位，变成两个 $01$ 矩阵，这样每次操作的 $x$ 也缩减到了 $\{0,1\}$ 两个数。

对于操作 $1$，选择 $x=1$ 显然是没有意义的，对于操作 $2$，选择 $x=0$ 显然也是没有意义的，于是每个操作就没有了 $x$ 之分，变成了将一行赋值为 $0$ 以及将一列赋值为 $1$ 两个简单的操作。

然后考虑每一个位置 $(i,j)$，如果 $A_{ij}\neq B_{ij}$，则肯定需要对第 $i$ 行或第 $j$ 列操作，具体如何操作依据 $B_{ij}$ 的值而定。

注意到操作和操作之间会互相影响，因此需要钦定一个合理的操作顺序，如果 $B_{ij}=1$，则对行 $i$ 的操作必须在对列 $j$ 操作前，反之亦然。我们发现这是一个二元关系，于是可以建出有向图，然后如果我们需要进行的操作代表的点出发可以走到环，那么肯定是无解的。

否则按照拓扑序，很容易构造出一组解。

至于有向图判环，dfs 或者 bfs 都可以。

时间复杂度（大概是）$O(Tnm\log V)$。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
int n, m, a[N][N], b[N][N];
vector<int> g[N << 1];
bool must[N << 1], vis[N], in[N];

bool dfs(int u){
    if(in[u]) return false;
    in[u] = 1;
    for(int v : g[u]){
        if(!vis[v] && !dfs(v)) return false;
    }
    in[u] = 0, vis[u] = 1;
    return true;
}

bool solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin >> a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin >> b[i][j];
    }
    for(int t=30;~t;t--){
        fill(must + 1, must + n + m + 1, 0);
        fill(vis + 1, vis + n + m + 1, 0);
        fill(in + 1, in + n + m + 1, 0);
        for(int i=1;i<=n+m;i++) g[i].clear();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                bool A = (a[i][j] >> t) & 1, B = (b[i][j] >> t) & 1;
                if(B) g[i].push_back(j + n);
                else g[j + n].push_back(i);
                if(A && !B) must[i] = 1;
                if(!A && B) must[j + n] = 1;
            }
        }
        for(int i=1;i<=n+m;i++){
            if(must[i] && !dfs(i)) if(!dfs(i)) return false;
        }
    }
    return true;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--) cout << (solve() ? "Yes" : "No") << '\n';
    return 0;
}

// Written by xiezheyuan