CTT 2026 - Ngày 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 CTT 2026 - Art 100 (p) 5.0s 1G
2 CTT 2026 - Balatro 100 (p) 2.0s 1G
3 CTT 2026 - Miracle 100 (p) 1.0s 1G

1. CTT 2026 - Art

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho các số nguyên dương \(n,m,k\) và một hoán vị \(p\) của \(1,2,\ldots,k\).

Một bức tranh là ma trận \(n\times m\) mà mỗi phần tử là một số nguyên trong \([1,k]\). Ký hiệu \(A_{i,j}\) là phần tử ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang.

Hai bức tranh \(A,B\) giống hệt nhau, ký hiệu \(A=B\), khi \(A_{i,j}=B_{i,j}\) với mọi \(1\le i\le n\), \(1\le j\le m\).

Hai bức tranh \(A,B\) tương tự nhau, ký hiệu \(A\sim B\), khi có thể biến \(A\) thành \(B\) bằng một số lần thực hiện một trong hai phép biến đổi:

  1. Chuyển hàng đầu tiên của \(A\) xuống thành hàng cuối cùng.
  2. Chuyển cột đầu tiên của \(A\) sang thành cột cuối cùng.

Có thể chứng minh rằng cả quan hệ giống hệt nhau và quan hệ tương tự nhau đều là quan hệ tương đương.

Với một bức tranh \(A\), định nghĩa bức tranh \(f(A)\) bởi

\[ f(A)_{i,j}=p_{A_{i,j}}. \]

Bức tranh \(A\) được gọi là đẹp khi và chỉ khi \(f(A)\sim A\).

Bạn cần trả lời hai câu hỏi:

  1. Có thể chọn nhiều nhất bao nhiêu bức tranh đẹp đôi một không giống hệt nhau?
  2. Có thể chọn nhiều nhất bao nhiêu bức tranh đẹp đôi một không tương tự nhau?

In các kết quả theo modulo \(998\,244\,353\).

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên dương \(n,m,k\).
  • Dòng thứ hai chứa \(k\) số nguyên \(p_1,p_2,\ldots,p_k\), là một hoán vị của \(1,2,\ldots,k\).

Dữ liệu ra

In hai dòng:

  • Dòng đầu là đáp án của câu hỏi 1 theo modulo \(998\,244\,353\).
  • Dòng thứ hai là đáp án của câu hỏi 2 theo modulo \(998\,244\,353\).

Bài có hai câu hỏi độc lập về điểm số. Dù chỉ giải một câu hỏi, bạn vẫn phải in đủ hai số theo đúng định dạng.

Ràng buộc

\[ 1\le n,m\le 10^3,\qquad 1\le k\le 10^6 \]

Với mọi \(1\le i\le k\), \(1\le p_i\le k\) và \(p_1,p_2,\ldots,p_k\) là một hoán vị của \(1,2,\ldots,k\).

Chấm điểm

Phần Điểm Giới hạn thêm
1 5 \(n,m\le 16\); \(nm\le 16\) và \(k\le 2\)
2 5 \(n,m\le 10^3\); \(p_i=i\) với mọi \(1\le i\le k\)
3 15 \(n,m\le 10^3\); \(n=1\)
4 20 \(n,m\le 50\); \(\gcd(n,m)=1\)
5 40 \(n,m\le 50\)
6 15 \(n,m\le 10^3\)

Trong từng phần:

  • Trả lời đúng câu hỏi 1 trên mọi dữ liệu nhận được \(70\%\) số điểm của phần.
  • Trả lời đúng câu hỏi 2 trên mọi dữ liệu nhận được \(30\%\) số điểm của phần.

Ví dụ

Ví dụ 1

Input 
4 4 2
2 1
Output 
774
60

Ví dụ 2

Input 
8 10 3
1 2 3
Output 
412733925
108590870

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

2. CTT 2026 - Balatro

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Sau khi đạt thành tựu "Completionist++" trong Balatro, bậc thầy Balatro Clonoth muốn kiểm tra hiểu biết của bạn về trò chơi thẻ bài.

Có một bộ bài gồm \(n\) lá. Mỗi mặt của mỗi lá ghi một số nguyên trong \([1,m]\). Bạn có thể chọn một số lá và lật chúng.

Với \(1\le l\le r\le m\), đoạn \([l,r]\) được gọi là có thể phủ nếu tồn tại một cách lật sao cho mỗi số nguyên trong \([l,r]\) xuất hiện trên mặt ngửa của ít nhất một lá.

Nói chính xác hơn, gọi hai số trên hai mặt của lá thứ \(i\) là \(a_{i,0},a_{i,1}\). Đoạn \([l,r]\) có thể phủ khi và chỉ khi tồn tại một xâu nhị phân \(s\) độ dài \(n\) sao cho với mọi \(l\le x\le r\), tồn tại \(1\le j\le n\) thỏa mãn \(a_{j,s_j}=x\).

Ban đầu bộ bài rỗng, tức \(n=0\). Sau đó có \(q\) thao tác thuộc một trong ba loại:

  1. Thêm lá: cho \(x,y\) (\(1\le x,y\le m\)). Tăng \(n\) lên \(1\), rồi thêm lá số \(n\) có mặt trước ghi \(x\) và mặt sau ghi \(y\).
  2. Loại lá: cho \(p\) (\(1\le p\le n\)), bảo đảm lá số \(p\) hiện vẫn còn trong bộ bài. Loại lá đó khỏi bộ bài.
  3. Truy vấn: cho \(s,t,u,v\) (\(1\le s\le t\le m\), \(1\le u\le v\le m\)). Đếm số đoạn \([l,r]\) thỏa mãn \(s\le l\le t\), \(u\le r\le v\) và \([l,r]\) có thể phủ.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên dương \(m,q\).
  • Mỗi dòng trong \(q\) dòng tiếp theo bắt đầu bằng số nguyên \(o\), là loại thao tác:
  • Nếu \(o=1\), dòng chứa 1 x y.
  • Nếu \(o=2\), dòng chứa 2 p.
  • Nếu \(o=3\), dòng chứa 3 s t u v.

Dữ liệu ra

Với mỗi truy vấn loại \(3\), in một số nguyên không âm trên một dòng: số đoạn thỏa mãn.

Ràng buộc

\[ 1\le m,q\le 2\cdot 10^5 \]

Mọi tham số của thao tác đều thỏa mãn các giới hạn nêu trong phần mô tả.

Chấm điểm

Phần Điểm Giới hạn thêm
1 30 \(m,q\le 2000\)
2 10 Tính chất A
3 10 Tính chất B và C
4 20 Tính chất B
5 20 Tính chất C
6 10 Không có giới hạn thêm
  • Tính chất A: mọi thao tác thêm và loại lá đều xuất hiện trước mọi truy vấn.
  • Tính chất B: không có thao tác loại lá.
  • Tính chất C: mọi truy vấn thỏa mãn \(s=t\) và \(u=v\).

Ví dụ

Ví dụ 1

Input 
8 10
1 6 5
3 2 3 8 8
1 3 3
1 4 5
3 2 6 6 8
1 1 2
2 4
1 2 5
3 1 3 2 7
3 2 3 2 3
Output 
0
2
8
3

Ví dụ 2

Input 
9 17
1 6 6
3 1 1 3 3
1 5 1
1 3 4
2 2
1 9 9
1 2 2
1 7 9
2 4
1 2 3
3 1 7 3 3
1 8 6
1 7 5
3 6 9 9 9
1 4 5
2 3
3 3 5 2 9
Output 
0
2
4
16

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

3. CTT 2026 - Miracle

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Ngày qua ngày, mọi thứ vận hành một cách máy móc; ba màu huỳnh quang đơn điệu xếp trước mắt, xung quanh là bóng tối nặng nề. Tương lai dường như chỉ dẫn đến một kết cục tồi tệ.

Sự trống rỗng hoàn toàn. Công việc máy móc tưởng như "đầy đủ" không thể lay chuyển mảnh đất tư tưởng cằn cỗi, dù những điều được nghĩ đến vẫn liên tục tạo ra các "kỳ tích" vô nghĩa.

Kỳ tích mà tôi mong đợi là gì? Có lẽ đó là một sự kiện xác suất nhỏ tác động đến nhiều bộ phận; các bộ phận ấy lại liên hệ với nhau và cuối cùng tạo nên một biến đổi lớn ở tầm vĩ mô.

Tháng nối tiếp tháng, bóng tối dần xâm lấn hy vọng. Trước nỗi tuyệt vọng gần như chắc chắn, tôi chỉ còn có thể cầu mong ánh sáng của kỳ tích lại xuất hiện.

Đông Tước nhận thấy nhiều sự vật tưởng như không liên quan vẫn có thể tạo ra những mối liên hệ kỳ diệu.

Một kỳ tích được biểu diễn bằng ma trận \(3\times3\) \(op\), trong đó \(op(i,j)\in\{0,1,2\}\) với mọi \(i,j\in\{0,1,2\}\).

Với \(0\le i,j<3^n\), viết biểu diễn cơ số \(3\) đủ \(n\) chữ số của chúng là

\[ i=(i_{n-1}\ldots i_1i_0)_3,\qquad j=(j_{n-1}\ldots j_1j_0)_3. \]

Định nghĩa

\[ i\oplus j=(k_{n-1}\ldots k_1k_0)_3,\qquad k_l=op(i_l,j_l)\quad(0\le l<n). \]

Ba dãy số nguyên không âm \(A,B,C\), mỗi dãy có độ dài \(3^n\), được gọi là chứa kỳ tích \(op\) nếu với mọi \(0\le i<3^n\),

\[ C_i=\sum_{j\oplus k=i} A_jB_k\pmod p,\qquad p=998\,244\,353. \]

Đông Tước có thể dễ dàng chọn ngẫu nhiên hai dãy \(A,B\) rồi tạo ra \(C\) sao cho ba dãy chứa một kỳ tích. Tuy nhiên, cậu ấy không biết kỳ tích đó là gì và muốn bạn tìm một đáp án khả dĩ.

Nói chính xác hơn, \(A_i\) và \(B_i\) được sinh độc lập, ngẫu nhiên đều trong \([0,p)\), và đề bảo đảm tồn tại ít nhất một ma trận \(op\) thỏa mãn công thức trên. Hãy tìm một ma trận như vậy.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test.

  • Dòng đầu chứa số nguyên dương \(t\), số bộ test.
  • Với mỗi bộ test:
  • Dòng đầu chứa số nguyên dương \(n\).
  • Dòng thứ hai chứa \(3^n\) số \(A_0,A_1,\ldots,A_{3^n-1}\).
  • Dòng thứ ba chứa \(3^n\) số \(B_0,B_1,\ldots,B_{3^n-1}\).
  • Dòng thứ tư chứa \(3^n\) số \(C_0,C_1,\ldots,C_{3^n-1}\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng chín số

\[ op(0,0),op(0,1),op(0,2),op(1,0),op(1,1),op(1,2),op(2,0),op(2,1),op(2,2). \]

Nếu có nhiều đáp án, in bất kỳ đáp án nào.

Ràng buộc

\[ 1\le t\le 16,\qquad 1\le n\le 10 \]
  • Các \(A_i\) độc lập và ngẫu nhiên đều trong \([0,p)\).
  • Các \(B_i\) độc lập và ngẫu nhiên đều trong \([0,p)\).
  • \(0\le C_i<p\).
  • Tồn tại ít nhất một \(op\) thỏa mãn.

Chấm điểm

Mỗi test trong bảng dưới đây có giá trị \(10\) điểm.

Test \(n\le\) Giới hạn thêm
1 1 Không có
2 3 Không có
3 5 Không có
4 10 Tính chất A
5 10 Tính chất B
6 10 Tính chất C
7 10 Tính chất D
8 10 Tính chất E
9 10 Tính chất F
10 10 Không có
  • Tính chất A: tồn tại \(x,y\in\{0,1,2\}\) sao cho
\[ op=\begin{pmatrix}x&x&x\\x&x&x\\y&y&y\end{pmatrix}. \]
  • Tính chất B: tồn tại \(x,y,z\in\{0,1,2\}\) sao cho
\[ op=\begin{pmatrix}x&x&x\\y&y&y\\z&z&z\end{pmatrix}. \]
  • Tính chất C: tồn tại \(x,y\in\{0,1,2\}\) sao cho
\[ op=\begin{pmatrix}x&x&y\\x&x&y\\y&y&y\end{pmatrix}. \]
  • Tính chất 😩 tồn tại \(a,b\in\{0,1,2\}\) sao cho \(op(i,j)=(ai+bj)\bmod3\) với mọi \(i,j\in\{0,1,2\}\).
  • Tính chất E: \(op(i,0)=op(i,1)\) với mọi \(i\in\{0,1,2\}\).
  • Tính chất F: \(op(i,j)\in\{0,1\}\) với mọi \(i,j\in\{0,1,2\}\).

Ví dụ

Ví dụ

Input 
3
1
2 0 2
1 0 0
2 2 0
2
0 0 1 1 1 2 0 0 2
1 0 0 2 1 0 1 2 2
10 10 6 8 5 2 8 9 5
3
0 0 0 1 0 1 1 1 1 2 2 2 2 1 0 2 2 0 0 0 1 1 0 2 1 0 2
2 2 1 2 2 0 1 0 1 1 1 0 1 1 1 0 1 1 0 2 0 0 2 1 1 1 0
70 0 81 0 0 0 124 0 105 0 0 0 0 0 0 0 0 0 11 0 101 0 0 0 25 0 108
Output 
1 2 0 0 0 0 0 0 0
1 1 1 0 2 0 0 1 2
0 2 2 0 0 0 2 2 2

Đầu vào của bài có thể lớn; nên sử dụng phương thức đọc dữ liệu nhanh.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.