Kiểm Tra Phép Nhân Ma Trận · canuc80k5604

Cho ba ma trận vuông $A, B, C$ cùng kích thước $n \times n$ . Mọi phép tính được thực hiện theo modulo $M = 1000000007$ .

Hãy xác định liệu $C$ có đúng là tích của $A$ và $B$ hay không. Nói cách khác, với mọi $1 \leq i, j \leq n$ , cần kiểm tra

C_{i, j} \equiv k = 1 \sum n A_{i, k} B_{k, j} (mod M) .

Input

Dòng đầu chứa số nguyên $n$ - kích thước của ba ma trận.
$n$ dòng tiếp theo mô tả ma trận $A$ ; mỗi dòng chứa $n$ số nguyên.
$n$ dòng tiếp theo mô tả ma trận $B$ theo cùng định dạng.
$n$ dòng cuối mô tả ma trận $C$ theo cùng định dạng.

Output

In YES nếu $A \cdot B \equiv C (mod M)$ theo từng phần tử; ngược lại, in NO.

Constraints

$1 \leq n \leq 1000$ .
$0 \leq A_{i, j}, B_{i, j}, C_{i, j} < M$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 35$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

YES

Giải thích: Ma trận $A$ là ma trận đơn vị, nên $A \cdot B = B$ ; các phần tử của $C$ đúng bằng các phần tử tương ứng của $B$ .

Test 2

Input

Output

NO

Giải thích: Phần tử ở hàng $2$ , cột $2$ của tích phải bằng $1$ , nhưng phần tử tương ứng của $C$ bằng $0$ , nên hai ma trận không bằng nhau theo modulo $M$ .

Ý tưởng: Nhân trực tiếp hai ma trận cần O(n^3) phép toán. Ta dùng kiểm tra Freivalds: chọn một vector ngẫu nhiên r, rồi so sánh
Ý tưởng: A · (B · r) và C · r theo modulo M.
Ý tưởng: Nếu A·B=C, hai vế bằng nhau với mọi r, nên thuật toán không bao giờ in NO sai. Nếu D=A·B-C khác ma trận không, lấy một hàng khác không của D. Sau khi cố định mọi tọa độ của r trừ một tọa độ có hệ số khác không, phương trình hàng đó của D·r=0 xác định nhiều nhất một giá trị còn lại. Vì mỗi tọa độ được chọn đều trong trường modulo M, xác suất một vòng bỏ sót không quá 1/M.
Ý tưởng: Lặp hai vòng độc lập làm xác suất bỏ sót không quá 1/M^2. Mỗi vòng thực hiện ba phép nhân ma trận-vector, nên tốn O(n^2) thời gian và O(n^2) bộ nhớ. Với subtask nhỏ, code tính tích trực tiếp để có kết quả tuyệt đối.