VM 14 Bài 09 - Nhân ma trận

Xem dạng PDF
Gửi bài giải
Điểm: 0,57 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~3~ ma trận ~A~, ~B~, ~C~ kích thước ~N \times N~. (~N \le 1000~), gồm các số nguyên từ ~0~ đến ~9~.

Các hàng của mỗi ma trận được đánh số từ ~1~ đến ~N~ từ trên xuống dưới. Các cột của mỗi ma trận được đánh số từ ~1~ đến ~N~ từ trái sang phải.

Phần tử ở hàng ~i~, cột ~j~ của ma trận ~A~ được ký hiệu là ~A~ (~i~, ~j~). Tương tự với ma trận ~B~ và ma trận ~C~.

Nhiệm vụ của bạn là kiểm tra đẳng thức ~A \times B~ = ~C~ đúng hay sai. Các phép tính được thực hiện trên module ~10~.

Phép ~A \times B~ ở đây là phép nhân ma trận, được định nghĩa như sau:

  • Với ma trận ~A~ kích thước ~m \times n~ và ma trận ~B~ kích thước ~n \times k~, kết quả của phép nhân là ma trận ~C~ kích thước ~m \times k~, với
  • ~C~ (~i~, ~j~) = ~\sum_{k = 1}^{n}~ ~A(i, k) \times B(k,j)~.

Input

Dòng ~1~: ~T~ - số test (~T \le 10~)

Tiếp theo là ~T~ test, mỗi test gồm:

  • Dòng ~1~: ~N~
  • ~N~ dòng tiếp, mỗi dòng ~N~ chữ số: ma trận ~A~
  • ~N~ dòng tiếp, mỗi dòng ~N~ chữ số: ma trận ~B~
  • ~N~ dòng tiếp, mỗi dòng ~N~ chữ số: ma trận ~C~

Output

Gồm ~T~ dòng, mỗi dòng YES / NO.

Giới hạn

  • ~20~% số test (tương ứng với ~20~% số điểm) có ~N \le 100~.
  • ~N \le 1000~.

Sample Input

2
2
12
34
43
21
85
03
2
12
34
43
21
85
00

Sample Output

YES
NO

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 3
    pppssslc  đã bình luận lúc 27, Tháng 7, 2025, 10:19

    My solve:

    Nhận xét 1:

    • Để nhân hai ma trận có kích thước ~n × m~ và ~m × k~ thì ta cần 1 thuật toán có độ phức tạp là ~O(n × m × k)~.
    • Áp dụng vào bài này thì thuật toán sẽ có độ phức tạp ~O(n^3)~ → TLE.
    • Vậy ta phải làm thế nào để đưa thuật toán về ~O(n^2)~ hay nhỏ hơn?

    Nhận xét 2:

    Nhân ma trận cũng có tính chất giao hoán và kết hợp giống phép nhân bình thường:

    • Nếu: ~A × B = C~
    • Thì: ~A × B × R = C × R~

    Cách làm:

    • Ta sẽ nhân ma trận ~A~ với ma trận ~R~ có kích thước ~n × 1~ ta sẽ thu được một ma trận kích thước ~n × 1~, sau đó ta nhân tiếp ma trận kết quả với ma trận ~B~, vì ma trận R có kích thước ~n × 1~ nên độ phức tạp sẽ là ~O(n^2)~.
    • Ta cũng nhân ma trận ~C~ với ma trận ~R~.
    • Rồi ta so sánh: ~A × B × R~ và ~C × R~.

    ⚠️ Lưu ý:

    Cách làm này có thể tồn tại sai số dẫn đến sai kết quả vậy nên ta nên thử lại nhiều lần để giảm thiểu sai số.

    ĐPT: ~O(n^2)~