trang chủ / đề bài / sqrttree

Tích ma trận trên đoạn

Đề bài

Mô tả

Cho dãy n ma trận vuông cấp 8: M1,M2,…,Mn, mọi phép tính trên phần tử đều lấy theo modulo p=109+7. Bạn cần trả lời q truy vấn, truy vấn thứ j hỏi tích

Pj=Mlj·Mlj+1⋯Mrj(modp)

theo đúng thứ tự từ trái sang phải (phép nhân ma trận không giao hoán).

Vì q 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 32 bit x, khởi tạo x=s. Mỗi lần gọi next() thực hiện lần lượt (mọi phép tính theo modulo 232, ⊕ là XOR bit, ≪ và ≫ là dịch bit):

  1. x←x⊕(x≪13);
  2. x←x⊕(x≫17);
  3. x←x⊕(x≪5);

rồi trả về x.

Sinh dãy ma trận. Với i=1,2,…,n theo thứ tự: gọi next() 64 lần để điền các phần tử của Mi theo từng hàng, từ hàng 1 đến hàng 8, trong mỗi hàng từ cột 1 đến cột 8; phần tử nhận giá trị next()modp. Sau đó gọi next() thêm một lần nữa: nếu giá trị này chẵn thì mọi phần tử ở hàng 8 của Mi được đặt bằng 0.

Sinh truy vấn. Đặt last=0. Với j=1,2,…,q theo thứ tự (sau khi đã sinh xong dãy ma trận):

  • gọi next() ba lần, lần lượt được u,v,w;
  • lj=((u⊕last)modn)+1;
  • t=(v⊕last)mod30;
  • nếu t<15 thì len=((w⊕last)mod2t)+1, ngược lại len=((w⊕last)modn)+1;
  • rj=min(n,lj+len−1);
  • tính Pj, gọi hj là XOR của cả 64 phần tử của Pj (mỗi phần tử là số nguyên trong [0,p));
  • gán last=hj.

Dữ liệu vào

Một dòng gồm ba số nguyên n, q, s.

Dữ liệu ra

In ra một số nguyên duy nhất là h1+h2+⋯+hq (tổng thông thường, không lấy modulo).

Ràng buộc

  • 1≤n≤3·104
  • 1≤q≤106
  • 1≤s<232

Ví dụ

Input Output Giải thích
4 3 1 879679202 Ba lần gọi next() đầu tiên trả về 270369, 67634689, 2647435461, nên M1 có hàng đầu bắt đầu bằng 270369,67634689,647435447,… Các ma trận M1,M3,M4 có hàng 8 bằng 0. Ba truy vấn là [4,4], [3,4], [2,3] với h=643923847, 156419387, 79335968; tổng là 879679202.
6 5 2026 3144942028 Các ma trận M2,M4 có hàng 8 bằng 0. Năm truy vấn là [4,4], [3,6], [6,6], [2,6], [2,6] với h=500904621, 854221906, 104443893, 842685804, 842685804.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0