Bảng

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.5s
Memory limit: 1G
Input: stdin
Output: stdout
Authors:
hohohaha, DatVu, LptN21, quangminh_0604, ducanh2706, trnthienphc2003, marvinthang, huyhasun, Ddoraaaaa
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

[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~.

image

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

Comments

Please read the guidelines before commenting.


  • 1
    RussVN123  commented on May 20, 2024, 11:28 a.m.

    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 ?


  • -1
    21ti_hdhphat  commented on Jan. 3, 2023, 2:51 a.m.

    Đề miêu tả cái truy vấn 2 sai kìa.


  • -9
    material_art_master  commented on Dec. 26, 2022, 4:14 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.