Chuyến đi vượt thời gian: Chapter VI (Temporal Reconstruction)

Tác giả:

Youtuber_TWK, p2o2HuaGiaBao, doangiaphuc13, thang16092012

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 2300 Thời gian: 1.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi hoàn thành Temporal Physics ở Chapter V, Youtuber_TWK, doangiaphuc13 và thang16092012 vẫn đứng trước cỗ máy thời gian.

Đột nhiên, toàn bộ hệ thống bật sáng.

TEMPORAL ARCHIVE DETECTED
ORIGIN: USSR — 1983
DESTINATION: USSR — 1963
NODE 01 — ACTIVE
NODE 02 — UNKNOWN
NODE 03 — ACTIVE
NODE 04 — CURRENT LOCATION

doangiaphuc13:

"1963?"

thang16092012:

"Nhưng chúng ta đang ở 1986."

Youtuber_TWK nhìn dòng dữ liệu.

"Tín hiệu được tạo ra năm 1983, nhưng đích đến lại là 1963."

Một dòng chữ mới xuất hiện:

TEMPORAL ANCHOR DETECTED
YEAR: 1963
NODE: 01

doangiaphuc13:

"Node 01?"

Youtuber_TWK:

"Có vẻ như đây là nơi mọi thứ bắt đầu."

thang16092012:

"Nhưng tại sao tín hiệu từ 1983 lại gửi ngược về 1963?"

Không ai trả lời.

Cỗ máy thời gian đột nhiên phát ra âm thanh cảnh báo.

TEMPORAL GATE: UNSTABLE
DESTINATION LOCKED: USSR — 1963
COUNTDOWN: 10

doangiaphuc13:

"Khoan, nó tự khởi động kìa!"

thang16092012:

"Có dừng được không?"

Youtuber_TWK:

"Không."

9
8
7

Anh nhìn hai người còn lại.

"Chuẩn bị đi."

6
5
4

Cả căn phòng rung lên.

3
2
1

Một luồng sáng bao phủ toàn bộ căn phòng.

USSR — 1963

Youtuber_TWK mở mắt.

Không còn Chernobyl.

Trước mặt họ là một khu nghiên cứu cũ của Liên Xô.

Trên cổng có dòng chữ:

USSR — SCIENTIFIC RESEARCH FACILITY
YEAR: 1963

doangiaphuc13:

"Chúng ta thật sự đến năm 1963 rồi."

thang16092012 nhìn phía sau.

Cỗ máy thời gian đã tắt hoàn toàn.

TEMPORAL GATE: CLOSED
RETURN PATH: LOCKED
CURRENT YEAR: 1963
NODE: 01

doangiaphuc13:

"Chúng ta bị kẹt rồi."

Youtuber_TWK:

"Vậy thì tìm Node 01."

Ba người tiến vào khu nghiên cứu.

Người thứ tư

Sau khi đi qua một hành lang phía sau khu nghiên cứu, họ bất ngờ gặp một người khác.

p2o2HuaGiaBao:

"Khoan!"

Cả ba quay lại.

doangiaphuc13:

"Cậu là ai?"

Người kia nhìn họ vài giây.

p2o2HuaGiaBao:

"Tôi là p2o2HuaGiaBao."

thang16092012:

"Cậu làm gì ở đây?"

p2o2HuaGiaBao:

"Tôi đang tìm một thứ."

Cậu lấy ra một mảnh kim loại cũ.

Trên đó có khắc:

NODE 01

doangiaphuc13:

"Cậu cũng đang tìm Node 01?"

p2o2HuaGiaBao:

"Đúng."

Youtuber_TWK:

"Vậy đi cùng chúng tôi."

p2o2HuaGiaBao:

"Các cậu biết nó ở đâu?"

Youtuber_TWK:

"Chưa."

"Nhưng chúng ta đang tìm cùng một thứ."

Bốn người tiếp tục tiến sâu vào khu nghiên cứu.

NODE 01

Cuối hành lang là một căn phòng điều khiển.

Bên trong chỉ có một chiếc máy tính cũ.

p2o2HuaGiaBao đặt mảnh kim loại lên bàn.

BÍP.

Màn hình bật sáng.

TEMPORAL NODE 01
STATUS: ACTIVE
SCANNING HUMAN SIGNATURES...
FOUR HUMAN SIGNATURES DETECTED

Một dòng chữ mới xuất hiện:

TEMPORAL RECONSTRUCTION PROTOCOL
INITIALIZING...

Sau vài giây:

CAN YOU RECONSTRUCT THE PAST?

Youtuber_TWK:

"Đây mới là bài kiểm tra thật sự."

Temporal Reconstruction

Node 01 mô phỏng một hệ thống tuyến tính gồm \(n\) trạng thái.

Tại thời điểm \(t\), hệ thống có vector hàng:

\[ v_t=(v_{t,1},v_{t,2},\ldots,v_{t,n}) \]

Hệ thống tiến hóa theo:

\[ v_{t+1}=v_tA \]

Trong đó \(A\) là ma trận chuyển trạng thái.

Giá trị quan sát tại thời điểm \(t\) được định nghĩa là:

\[ x_t=v_tw \]

Do đó:

\[ x_t=v_0A^tw \]

Các phần tử của \(A\) và \(w\) được cho dưới dạng phân số.

Ma trận \(A\) thỏa mãn:

\[ A_{i,j}=\frac{a_{i,j}}q \]

Vector quan sát thỏa mãn:

\[ w_i=\frac{b_i}q \]

Tất cả phép tính được thực hiện modulo:

\[ MOD=10^9+7 \]

Mọi phép chia cho \(q\) được hiểu là nhân với nghịch đảo modulo của \(q\).

Cụ thể:

\[ A_{i,j}=a_{i,j}\cdot q^{-1}\pmod{MOD} \]

và:

\[ w_i=b_i\cdot q^{-1}\pmod{MOD} \]

trong đó \(q^{-1}\) là số thỏa mãn:

\[ q\cdot q^{-1}\equiv1\pmod{MOD} \]

Đề bài đảm bảo:

\[ \gcd(q,MOD)=1 \]

nên nghịch đảo modulo của \(q\) luôn tồn tại.

Các truy vấn

Vector ban đầu \(v_0\) và ma trận \(A\) không thay đổi trong suốt quá trình.

Chỉ vector quan sát \(w\) có thể thay đổi.

Truy vấn loại 1

Dạng:

\[ 1\ b_1\ b_2\ \ldots\ b_n \]

Thay vector quan sát hiện tại bằng vector có các phần tử:

\[ w_i=b_i\cdot q^{-1}\pmod{MOD} \]

Các giá trị \(b_i\) trong truy vấn mới không liên quan đến các giá trị \(b_i\) của vector quan sát ban đầu.

Truy vấn loại 2

Dạng:

\[ 2\ T \]

Yêu cầu tính:

\[ x_T=v_0A^Tw \]

với vector quan sát \(w\) hiện tại.

In kết quả modulo:

\[ MOD=10^9+7 \]

Linear Recurrence

Do hệ thống có \(n\) trạng thái, dãy:

\[ x_0,x_1,x_2,\ldots \]

luôn thỏa mãn một truy hồi tuyến tính có bậc không vượt quá \(n\).

Tồn tại \(k\le n\) và các hệ số \(c_1,c_2,\ldots,c_k\) sao cho:

\[ x_t=c_1x_{t-1}+c_2x_{t-2}+\cdots+c_kx_{t-k} \]

với mọi \(t\ge k\).

Các hệ số \(c_i\) và mọi phép tính trong truy hồi đều được thực hiện modulo \(MOD\).

Vì \(T\) có thể lên tới \(10^{18}\), không thể tính lần lượt từ \(x_0\) đến \(x_T\).

Có thể sử dụng Berlekamp-Massey để tìm truy hồi nhỏ nhất của dãy, sau đó sử dụng Kitamasa hoặc binary polynomial exponentiation để tính \(x_T\).

Một điểm quan trọng là \(v_0\) và \(A\) không thay đổi giữa các truy vấn.

Có thể tính trước:

\[ v_0,v_1,\ldots,v_{2n} \]

với:

\[ v_{t+1}=v_tA \]

Sau đó, với vector quan sát \(w\) hiện tại, xây dựng:

\[ x_t=v_tw \]

trên các vector đã tính.

Nếu dãy quan sát thu được toàn bằng \(0\), mọi truy vấn loại \(2\) tương ứng đều có đáp án \(0\).

Độ phức tạp

Một cách giải đạt độ phức tạp:

\[ O(n^3+Qn^2\log T) \]

và bộ nhớ:

\[ O(n^2) \]

Input

Dòng đầu tiên chứa ba số nguyên:

\[ n\ Q\ q \]

Trong đó:

\(n\) là số trạng thái.
\(Q\) là số truy vấn.
\(q\) là mẫu số chung.

Dòng thứ hai chứa \(n\) số nguyên:

\[ s_1\ s_2\ \ldots\ s_n \]

là vector trạng thái ban đầu:

\[ v_0=(s_1,s_2,\ldots,s_n) \]

\(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên:

\[ a_{i,1}\ a_{i,2}\ \ldots\ a_{i,n} \]

biểu diễn ma trận chuyển trạng thái:

\[ A_{i,j}=\frac{a_{i,j}}q \]

Dòng tiếp theo chứa \(n\) số nguyên:

\[ b_1\ b_2\ \ldots\ b_n \]

biểu diễn tử số của vector quan sát ban đầu:

\[ w_i=b_i\cdot q^{-1}\pmod{MOD} \]

\(Q\) dòng tiếp theo chứa các truy vấn.

Truy vấn loại \(1\) có dạng:

\[ 1\ b_1\ b_2\ \ldots\ b_n \]

Truy vấn loại \(2\) có dạng:

\[ 2\ T \]

Output

Với mỗi truy vấn loại \(2\), in một dòng chứa:

\[ v_0A^Tw\pmod{10^9+7} \]

Constraints

\(1\le n\le200\)
\(1\le Q\le50\)
\(0\le s_i\le10^{18}\)
\(0\le a_{i,j}\le10^9\)
\(0\le b_i\le10^9\)
\(1\le q\le10^9\)
\(0\le T\le10^{18}\)
\(\gcd(q,10^9+7)=1\)

Example

Test 1

Input

Output

47
76
3

Note

Ban đầu:

\[ v_0=(1,0) \]

và:

\[ A= \begin{pmatrix} 2&1\\ 1&1 \end{pmatrix} \]

Vector quan sát ban đầu:

\[ w=(1,2) \]

Ta có:

\[ A^5= \begin{pmatrix} 21&13\\ 13&8 \end{pmatrix} \]

nên:

\[ v_0A^5=(21,13) \]

Do đó:

\[ x_5=(21,13) \begin{pmatrix} 1\\ 2 \end{pmatrix} =47 \]

Sau truy vấn loại \(1\), vector quan sát trở thành:

\[ w=(3,1) \]

Vì vậy:

\[ x_5=(21,13) \begin{pmatrix} 3\\ 1 \end{pmatrix} =76 \]

Cuối cùng với \(T=0\):

\[ x_0=v_0w=3 \]

Màn hình im lặng.

RECONSTRUCTION SYSTEM: READY
TEMPORAL RECONSTRUCTION
PROCESSING...
NODE 01: LOCKED
HISTORICAL DATA: INCOMPLETE
RECOVER THE PAST.

doangiaphuc13 nhìn hàng loạt công thức trên màn hình.

"Lại một bài toán..."

thang16092012:

"Lần này còn khó hơn cái ở Chernobyl."

p2o2HuaGiaBao:

"Nếu không khôi phục được dữ liệu thì sao?"

Youtuber_TWK nhìn màn hình.

"Thì chúng ta sẽ không biết chuyện gì đã xảy ra."

Anh đặt tay lên bàn phím.

"Bắt đầu thôi."

Màn hình hiện:

TEMPORAL RECONSTRUCTION
PROCESSING...

Một dòng dữ liệu cuối cùng xuất hiện:

NODE 01: ACCESSING ARCHIVE...
YEAR: 1963
PROJECT: ██████████
NEXT RECORD: 1972

Cả bốn người nhìn nhau.

doangiaphuc13:

"Khoan..."

thang16092012:

"Node 01 không phải điểm kết thúc."

p2o2HuaGiaBao:

"Mà là điểm bắt đầu."

Youtuber_TWK nhìn dòng chữ NEXT RECORD: 1972.

"Vậy thì..."

Anh nhấn Enter.

ACCESS DENIED.
REQUIRED NODE: 02

Cánh cửa phía cuối phòng đột nhiên mở ra.

Bên trong là một hành lang tối.

Ở cuối hành lang, một bóng đèn đỏ đang nhấp nháy.

BÍP.

NODE 02: ACTIVE

Câu chuyện vẫn chưa kết thúc!!!!

Chuyến đi vượt thời gian: Chapter VII (Secret Project)

Bình luận (1)

Tải bình luận...