D - A mul B Problem

Time Limit: 5 sec / Memory Limit: 128 MB

問題文

Kはある大学で線形代数の講師をしている。 基礎学力を重視するKは生徒に行列の掛け算の問題のレポートを出した。 しかし、Kは授業の予習、サークルの顧問、中間試験の作成などで、レポートの採点をする時間がない。 TAであるあなたはKからレポートの採点を頼まれた。あなたの仕事は N \times N 行列 A,B,C が与えられた時に、A \times B = C であるかどうかをチェックすることである。

入力形式

入力は以下の形式で与えられる。

N
A_{11} A_{12} ... A_{1N}
A_{21} A_{22} ... A_{2N}
...
A_{N1} A_{N2} ... A_{NN}
B_{11} B_{12} ... B_{1N}
B_{21} B_{22} ... B_{2N}
...
B_{N1} B_{N2} ... B_{NN}
C_{11} C_{12} ... C_{1N}
C_{21} C_{22} ... C_{2N}
...
C_{N1} C_{N2} ... C_{NN}

出力形式

A \times B = Cを 満たすならYES、満たさないならNOを一行に出力せよ。

制約

  • 1 \leq N \leq 1000
  • -1,000 \leq a_{ij}, b_{ij} \leq 1,000
  • -10^9 \leq c_{ij} \leq 10^9
  • 入力値はすべて整数である.

この問題の判定には,99 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.

  • N = 1

入出力例

入力例1

1
1
2
2

出力例1

YES

入力例2

3
1 0 0
0 1 0
0 0 1
0 0 1
0 1 0
1 0 0
-1 -1 -1
-1 -1 -1
-1 -1 -1

出力例2

NO

入力例3

3
1 2 3
4 5 6
7 8 9
11 12 13
14 15 16
17 18 19
90 96 102
216 231 246
342 366 390

出力例3

YES

ヒント

似たような問題
プログラミングコンテストでの乱択アルゴリズム


Writer : 森槙悟
Tester : 楠本充

Source Name

KUPC 2012 Practice