题目解析

问题重述

给定两个 $n \times m$ 的矩阵 $A$ 和 $B$，元素范围 $[0, 10^9]$。允许两种操作：

1. 行与操作：选择行 $i$ 和整数 $x \ge 0$，将该行每个元素 $A_{i,j}$ 替换为 $A_{i,j} \ \&\ x$
2. 列或操作：选择列 $j$ 和整数 $x \ge 0$，将该列每个元素 $A_{i,j}$ 替换为 $A_{i,j} \ | \ x$

问能否通过任意次操作将 $A$ 变为 $B$。

核心思路

1. 按位独立处理

由于位运算（AND、OR）的每一位是独立的，我们可以分别考虑每个二进制位（$0$ 到 $29$ 位，因为 $10^9 < 2^{30}$）。对于每个位，问题转化为：

• 给定两个二进制矩阵 $A$ 和 $B$（只包含 $0$ 和 $1$）
• 操作：
  • 将某行全部设为 $0$（对应 AND 操作，取 $x$ 该位为 $0$）
  • 将某列全部设为 $1$（对应 OR 操作，取 $x$ 该位为 $1$）

2. 必要操作分析

对于每个位置 $(i, j)$，比较 $A_{i,j}$ 和 $B_{i,j}$（当前位）：

• 若 $A_{i,j} = 0, B_{i,j} = 1$：该位从 $0$ 变 $1$，只能通过列 OR 操作实现，因此第 $j$ 列必须执行 OR 操作
• 若 $A_{i,j} = 1, B_{i,j} = 0$：该位从 $1$ 变 $0$，只能通过行 AND 操作实现，因此第 $i$ 行必须执行 AND 操作
• 若 $A_{i,j} = B_{i,j}$：没有强制要求，但后续操作可能改变它

3. 操作之间的依赖关系

考虑一个位置 $(i, j)$ 且 $B_{i,j} = 0$：

• 如果对第 $j$ 列执行了 OR 操作，该位置会变成 $1$，不符合要求
• 因此，若对第 $j$ 列执行 OR 操作，则必须随后对第 $i$ 行执行 AND 操作，将其改回 $0$
• 这形成依赖：列 OR $\rightarrow$ 行 AND

类似地，若 $B_{i,j} = 1$：

• 如果对第 $i$ 行执行 AND 操作，该位置会变成 $0$，不符合要求
• 因此，若对第 $i$ 行执行 AND 操作，则必须随后对第 $j$ 列执行 OR 操作
• 这形成依赖：行 AND $\rightarrow$ 列 OR

4. 构建依赖图

• 创建 $n + m$ 个节点：
  • 节点 $0 \dots n-1$ 表示行 AND 操作
  • 节点 $n \dots n+m-1$ 表示列 OR 操作
• 添加有向边：
  • 若 $B_{i,j} = 0$：添加边 $j + n \rightarrow i$（列 OR 必须先于行 AND）
  • 若 $B_{i,j} = 1$：添加边 $i \rightarrow j + n$（行 AND 必须先于列 OR）

5. 必须执行的操作

• 若有位置 $A_{i,j} = 1, B_{i,j} = 0$，则行 $i$ 的 AND 操作必须执行
• 若有位置 $A_{i,j} = 0, B_{i,j} = 1$，则列 $j$ 的 OR 操作必须执行

6. 可行性判断

从每个必须执行的操作节点出发，检查是否存在有向环：

• 如果存在环，意味着操作之间存在循环依赖，无法满足所有要求 → 该位不可行
• 如果没有环，则可以按拓扑序执行操作，得到正确结果

环检测使用三色 DFS：

• 0：未访问
• 1：正在 DFS 栈中（当前路径）
• 2：已完全处理

若在 DFS 中遇到状态为 1 的节点，说明找到环。

7. 最终答案

所有 $30$ 个位都可行时输出 Yes，否则输出 No。

算法步骤

1. 对于每个测试用例：
2. 对于每个位 $k$（$0 \le k < 30$）：
   • 构建 $n + m$ 个节点的图
   • 遍历所有 $n \times m$ 个位置：
     • 比较 $A_{i,j}$ 和 $B_{i,j}$ 的第 $k$ 位
     • 记录必须执行的行/列操作
     • 根据 $B_{i,j}$ 的当前位添加依赖边
   • 从每个必须执行的操作节点出发进行 DFS 环检测
   • 如果有环，该位不可行，输出 No
3. 所有位都可行，输出 Yes

示例验证

例2： $n=2, m=2$

初始 $A$：

10 10
42 42

$B$：

21 21
21 21

二进制表示（低位在右）：

• $10 = 1010_2$，$42 = 101010_2$，$21 = 10101_2$

按位分析：

• 对于第 $0$ 位（$2^0$）：$A$ 全是 $0$，$B$ 全是 $1$ → 需要列 OR
• 无环 → 可行

所有位都可行 → Yes

时间复杂度

• 每位 $O(n \cdot m)$ 建图 + $O(n + m)$ DFS
• 共 $30$ 位，$n \cdot m \le 1000$，$t \le 100$
• 总复杂度 $O(t \cdot 30 \cdot n \cdot m) \approx 3 \times 10^6$，非常快

C++ 代码

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

struct Graph {
    int V;
    vector<vector<int>> g;
    vector<int> color;
    
    bool dfs(int v) {
        if (color[v] != 0) return false;
        color[v] = 1;
        bool has_cycle = false;
        for (int u : g[v]) {
            if (color[u] == 2) continue;
            if (color[u] == 0) {
                has_cycle |= dfs(u);
            } else {
                has_cycle = true;
            }
        }
        color[v] = 2;
        return has_cycle;
    }
    
    void add_edge(int x, int y) {
        g[x].push_back(y);
    }
    
    Graph(int V) : V(V), g(V), color(V, 0) {}
};

int get_bit(int x, int k) {
    return (x >> k) & 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, false);
    vector<bool> must_col(m, false);
    
    Graph G(n + m);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a_bit = get_bit(A[i][j], k);
            int b_bit = get_bit(B[i][j], k);
            
            // 必须执行的操作
            if (a_bit != b_bit) {
                if (b_bit == 0) must_row[i] = true;
                else must_col[j] = true;
            }
            
            // 添加依赖边
            if (b_bit == 0) {
                // B[i][j] = 0: 列 OR 必须先于行 AND
                G.add_edge(j + n, i);
            } else {
                // B[i][j] = 1: 行 AND 必须先于列 OR
                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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector<vector<int>> A(n, vector<int>(m));
        vector<vector<int>> B(n, vector<int>(m));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> A[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> B[i][j];
            }
        }
        
        bool ok = true;
        for (int k = 0; k < 30; k++) {
            if (!check(A, B, k)) {
                ok = false;
                break;
            }
        }
        
        cout << (ok ? "Yes" : "No") << '\n';
    }
    
    return 0;
}

关键点总结

1. 按位独立：位运算的每一位独立，降低问题复杂度
2. 二元操作：每位上只有 AND 行（设 $0$）和 OR 列（设 $1$）两种操作
3. 依赖关系：根据目标值 $B_{i,j}$ 确定操作顺序约束
4. 有向图环检测：必须执行的操作若导致循环依赖，则不可行
5. 三色 DFS：高效检测有向环，同时避免重复处理

注意事项

• 每个操作可以应用多次，但后一次覆盖前一次，所以只需考虑最后是否执行
• 操作顺序很重要：先执行的操作可能被后续操作覆盖
• $n \cdot m \le 1000$，因此 $O(n \cdot m \cdot 30)$ 完全可以接受
• 使用 cin/cout 时记得 ios::sync_with_stdio(false) 加速