本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-27 12:12:28

题意

给定大小为 $n \times m$ 的矩阵 $A,B$，两个矩阵均由不大于 $10^9$ 的非负整数组成。

单次操作可以有以下两种形式：

1. 选择两个数 $i,x$，满足 $1 \le i \le n,x \ge 0$。

   对于 $1 \le \forall j \le m$，将 $A_{i,j}$ 替换为 $A_{i,j}$ 按位与 $x$，即整行按位与。

2. 选择两个数 $j,x$，满足 $1 \le j \le m,x\ge 0$。

   对于 $1 \le \forall i \le n$，将 $A_{i,j}$ 替换为 $A_{i,j}$ 按位或 $x$，即整列按位或。

问能否在任意次操作之后将 $A$ 变为 $B$。

做法

每一位都是独立的，考虑枚举每一位。

问题简化为了，两个 $n \times m$ 的 01 矩阵 $A,B$，每次可以将 $A$ 的一整行设置为 $0$，或将 $A$ 的一整列设置为 $1$，求能否将 $A$ 变为 $B$。

考虑对于 $(i,j)$，如果 $A_{i,j} \neq B_{i,j}$，该如何处理。

1. $A_{i,j}=1$ 且 $B_{i,j}=0$，此时需要对 $i$ 行执行一次操作。
2. $A_{i,j}=0$ 且 $B_{i,j}=1$，此时需要对 $j$ 列进行一次操作。

不难注意到，每一行，每一列最多执行一次操作。

如果对第 $i$ 行执行了操作，且存在 $j$ 满足 $B_{i,j}=1$，那么必然需要在此之后对 $j$ 列执行一次操作。

同理，如果对第 $j$ 列执行了操作，存在 $i$ 满足 $B_{i,j}=0$，那么必然需要在此之后对第 $i$ 列执行一次操作。

由此可以建立一个有向图，$x \rightarrow y$ 代表 $x$ 操作执行完成后必须执行 $y$ 操作。

从每个必须执行的操作出发 dfs，如果找到环，那么必然无解。

如果最终没有找到环，显然是有解的。