VOI 22 Bài 6 - Xây dựng ma trận

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: MATRIX.INP
Output: MATRIX.OUT

Problem source:
Kỳ thi Học sinh giỏi Quốc gia 2022 - Ngày 2
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Để xây dựng thêm chức năng biến đổi ảnh cho phần mềm vẽ, Nam cần xây dựng ma trận ~A~ có tính chất sau:

  • Ma trận có ~m~ hàng và ~n~ cột, các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Phần tử nằm ở hàng ~i~ (~1 \le i \le m~) và cột ~j~ (~1 \le j \le n~) kí hiệu là ~A_{i,j}~, giá trị mỗi phần tử của ma trận đều là các số nguyên dương;
  • Hai phần tử cùng hàng nhưng có chỉ số cột là nguyên tố cùng nhau thì giá trị phải khác nhau. Cụ thể: với ~1 \le j_1, j_2 \le n~ và ước số chung lớn nhất của ~(j_1, j_2)~ bằng ~1~ thì ~A_{i,j_1}~ khác ~A_{i,j_2}~ với mọi ~i~ (~1 \le i \le m~);
  • Hai phần tử cùng cột nhưng có chỉ số hàng là nguyên tố cùng nhau thì giá trị phải khác nhau. Cụ thể: với ~1 \le i_1, i_2 \le m~ và ước số chung lớn nhất của ~(i_1, i_2)~ bằng ~1~ thì ~A_{i_1,j}~ khác ~A_{i_2,j}~ với mọi ~j~ (~1 \le j \le n~);
  • Thứ tự từ điển của ma trận là nhỏ nhất có thể.

Ma trận ~A~ được gọi là có thứ tự từ điển nhỏ hơn ma trận ~B~ (hai ma trận cùng có ~m~ hàng và ~n~ cột) nếu lần lượt so sánh từng phần tử theo từng hàng từ trên xuống dưới, trên mỗi hàng theo thứ tự từ trái sang phải để tìm phần tử khác nhau đầu tiên thì tại vị trí đó giá trị phần tử của ma trận ~A~ nhỏ hơn giá trị phần tử của ma trận ~B~.

Yêu cầu: Cho ~m~ và ~n~, gọi ~S~ là tổng các phần tử của ma trận, hãy tính ~S \bmod (10^9 + 7)~, trong đó ~\bmod~ là phép toán chia lấy dư.

Dữ liệu

Vào từ file văn bản MATRIX.INP gồm một dòng duy nhất chứa hai số nguyên dương ~m~, ~n~ cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản MATRIX.OUT một số nguyên duy nhất là ~S \bmod (10^9 + 7)~.

Ràng buộc

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~m \times n \le 10^4~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~m = 1, n \le 10^9~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m, n\le 10^6~;
  • ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài thỏa mãn: ~m, n\le 10^9~.

Ví dụ 1

Input
1 3
Output
6
Giải thích

Ma trận thỏa mãn cần tìm là:

$$\begin{array}{ccc} 1& 2& 3 \end{array}$$

Ví dụ 2

Input
3 3
Output
21
Giải thích

Ma trận thỏa mãn cần tìm là:

$$\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 4 \\ 3 & 4 & 1 \end{array}$$


Comments

Please read the guidelines before commenting.



  • -3
    nogo007akapkn  commented on March 3, 2024, 4:51 p.m.

    xin 1 downvote ạ