Tích ma trận trên đoạn
Đề bài
Mô tả
Cho dãy ma trận vuông cấp : , mọi phép tính trên phần tử đều lấy theo modulo . Bạn cần trả lời truy vấn, truy vấn thứ hỏi tích
theo đúng thứ tự từ trái sang phải (phép nhân ma trận không giao hoán).
Vì rất lớn, cả dãy ma trận lẫn các truy vấn đều được sinh bằng một bộ sinh số giả ngẫu nhiên, và mỗi truy vấn phụ thuộc vào đáp án của truy vấn ngay trước nó.
Bộ sinh. Trạng thái là một số nguyên không dấu bit , khởi tạo . Mỗi lần gọi thực hiện lần lượt (mọi phép tính theo modulo , là XOR bit, và là dịch bit):
- ;
- ;
- ;
rồi trả về .
Sinh dãy ma trận. Với theo thứ tự: gọi lần để điền các phần tử của theo từng hàng, từ hàng đến hàng , trong mỗi hàng từ cột đến cột ; phần tử nhận giá trị . Sau đó gọi thêm một lần nữa: nếu giá trị này chẵn thì mọi phần tử ở hàng của được đặt bằng .
Sinh truy vấn. Đặt . Với theo thứ tự (sau khi đã sinh xong dãy ma trận):
- gọi ba lần, lần lượt được ;
- ;
- ;
- nếu thì , ngược lại ;
- ;
- tính , gọi là XOR của cả phần tử của (mỗi phần tử là số nguyên trong );
- gán .
Dữ liệu vào
Một dòng gồm ba số nguyên , , .
Dữ liệu ra
In ra một số nguyên duy nhất là (tổng thông thường, không lấy modulo).
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 1 | 879679202 | Ba lần gọi đầu tiên trả về , , , nên có hàng đầu bắt đầu bằng Các ma trận có hàng bằng . Ba truy vấn là , , với , , ; tổng là . |
| 6 5 2026 | 3144942028 | Các ma trận có hàng bằng . Năm truy vấn là , , , , với , , , , . |
https://oj.chuyentin.pro/problem/sqrttree
Bình luận