QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#10520. 矩陣除法

Statistics

對於 $n \times m$ 的 01 矩陣 $A$ 和 $m \times p$ 的 01 矩陣 $B$,定義它們的乘積為一個 $n \times p$ 的 01 矩陣 $C$。其中,$C_{i,j} = \bigoplus_{k=1}^{m} A_{i,k} \& B_{k,j} \ ^\dagger$。

現在,Link 希望進行乘法的逆運算——除法。給定 $n \times m$ 的 01 矩陣 $A$ 和 $n \times p$ 的 01 矩陣 $C$,你需要找到一個 $m \times p$ 的矩陣 $B$,使得 $A$ 與 $B$ 的乘積恰好等於 $C$。

$^\dagger \oplus$ 表示按位異或運算,$\&$ 表示按位與運算。例如:$(0011)_2 \oplus (0101)_2 = (0110)_2$,$(0011)_2 \& (0101)_2 = (0001)_2$。

輸入格式

每個測試檔案僅有一組測試資料。

第一行包含三個整數 $n, m, p$ ($1 \le n, m, p \le 1000$)。

接下來 $n$ 行,第 $i$ 行包含 $m$ 個整數 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$ ($A_{i,j} \in \{0, 1\}$),表示矩陣 $A$ 的元素。

接下來 $n$ 行,第 $i$ 行包含 $p$ 個整數 $C_{i,1}, C_{i,2}, \dots, C_{i,p}$ ($C_{i,j} \in \{0, 1\}$),表示矩陣 $C$ 的元素。

輸出格式

如果不存在滿足條件的矩陣 $B$,請輸出 “No”。

如果存在滿足條件的矩陣 $B$,請在第一行輸出 “Yes”,然後輸出 $m$ 行,每行 $p$ 個整數 $B_{i,1}, B_{i,2}, \dots, B_{i,p}$ ($B_{i,j} \in \{0, 1\}$),表示你找到的 $B$ 矩陣。

如果存在多個滿足條件的矩陣 $B$,你可以輸出任何一個。

範例

範例 1

3 2 3
1 0
1 1
1 0
0 0 0
0 1 0
0 0 0
Yes
0 0 0
0 1 0

範例 2

3 2 3
1 0
1 1
1 0
1 0 0
0 1 0
0 0 1
No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.