Bảng
Xem dạng PDF
[placeholder] đã ngồi nghĩ 3 ngày 3 đêm nhưng không ra được cốt truyện cho bài này.
Cho bảng ~M~ kích thước ~n \times n~ gồm các số nguyên dương. Bạn phải xử lý ~q~ truy vấn gồm 2 loại:
- ~1\; x\; y\; z~: Tìm số lớn nhất trong bảng con ~z \times z~ có góc trên-trái là ô ~(x,y)~. Ô trên-trái của bảng là ô ~(1,1)~.
- ~2\; x\; y~: Dịch (cyclic shift) bảng ~x~ ô theo chiều dọc và ~y~ ô theo chiều ngang. Hình dưới minh họa bảng ~4 \times 4~ với ~x=2~ và ~y=1~.
Lưu ý: Do kích thước lớn, để giảm thời gian nhập-xuất, input-output của bài toán được xử lý đặc biệt.
Input
Dòng đầu tiên chứa 2 số ~n, q~ (~n \leq 1,000~, ~q \leq 2,000,000~).
Dòng tiếp theo chứa 2 số ~A_0, B_0~ (~A, B < 10^9+7~).
Dòng cuối cùng chứa 4 số ~C_0, D_0, E_0, F_0~ (~C < 10^9+7, D, E, F < n~).
Với ~i \geq 1~:
Các dãy ~A, B, C~ được định nghĩa như sau:
- ~X_1~ = ~1+((X_0*X_0)\; mod\; 10^9+7)~
- ~X_i~ = ~1+((X_{i-1}+X_{i-2})\; mod\; 10^9+7)\; (i \geq 2)~
Các dãy ~D, E, F~ được định nghĩa như sau:
- ~X_1~ = ~1+((X_0*X_0)\; mod\; n)~
- ~X_i~ = ~1+((X_{i-1}+X_{i-2})\; mod\; n)\; (i \geq 2)~
Dãy ~L~ được định nghĩa như sau: ~L_i = n-max(D_i,E_i)~
Bảng ~M~ được tính bằng công thức:
- ~a_{i,j}: (A_i + B_j)\; mod \; 10^9+7~
Với truy vấn thứ ~i~, nếu ~C_i\; \&\; 1=0~ thì truy vấn đó sẽ có dạng:
- ~1\; D_i\; E_i\; [1+(L_i\; \&\; (L_i \oplus F_i))]~
Ngược lại, nếu ~C_i\; \&\; 1=1~ thì truy vấn đó sẽ có dạng:
- ~2\; D_i\; E_i~
Trong đó: ~\&, \oplus~ là toán tử AND, XOR
Output
Với mỗi ~1,000~ truy vấn loại 1, ta in ra tổng đáp án của các truy vấn đó ~mod\; 10^9+7~ trên các dòng khác nhau.
Ví dụ: Với test có ~3456~ truy vấn loại 1, output có dạng như sau:
~(ans_1\; +\; ...\; +\; ans_{1000})\; mod\; 10^9+7~
~(ans_{1001}\;+\;...\;+\;ans_{2000})\; mod\; 10^9+7~
~(ans_{2001}\;+\;...\;+\;ans_{3000})\; mod\; 10^9+7~
~(ans_{3001}\;+\;...\;+\;ans_{3456})\; mod\; 10^9+7~
Sample Input 1
7 10
2 3
177013 4 5 6
Sample Output 1
262
Notes
Giải thích ví dụ 1:
Bảng số :
| 15 | 19 | 30 | 45 | 71 | 112 | 179 |
| 18 | 22 | 33 | 48 | 74 | 115 | 182 |
| 24 | 28 | 39 | 54 | 80 | 121 | 188 |
| 33 | 37 | 48 | 63 | 89 | 130 | 197 |
| 48 | 52 | 63 | 78 | 104 | 145 | 212 |
| 72 | 76 | 87 | 102 | 128 | 169 | 236 |
| 111 | 115 | 126 | 141 | 167 | 208 | 275 |
Các truy vấn:
| 2 3 5 |
| 2 1 4 |
| 2 5 3 |
| 1 7 1 1 |
| 1 6 5 1 |
| 2 7 7 |
| 2 7 6 |
| 1 1 7 1 |
| 1 2 7 1 |
| 2 4 1 |
Bình luận
bộ test dịch hàng thì qua phải mà sao trên kia vẽ bảng lại qua trái vậy mọi người ?
Đề miêu tả cái truy vấn 2 sai kìa.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.