Ô Vuông

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (Tin học trẻ bảng C2 Cần Thơ 2024) Độ khó: Trung bình Quy hoạch động đếm Tổ hợp

Đề bài

Cho các số nguyên dương $K, N$ với $K < N$ và bảng ô vuông $2 \times N$ như hình bên dưới.

Tính số cách chọn $K$ ô vuông trong bảng sao cho không có hai ô vuông nào chung đỉnh. Do kết quả có thể rất lớn, in ra kết quả sau khi đã chia lấy dư cho $10^9 + 7$.

Biết rằng, hai ô có chung đỉnh là hai ô có chung ít nhất một trong bốn đỉnh. Bên dưới là 2 ví dụ về hai ô có chung đỉnh:

Giới hạn chung: $1 \le K < N \le 10^5$.

Ràng buộc:

• Ràng buộc 1 (40% số điểm): $1 \le K < N \le 10$.
• Ràng buộc 2 (20% số điểm): $10 < K < N \le 10^3$.

Đầu vào: một dòng duy nhất chứa hai số nguyên $K$ và $N$.

Đầu ra: một số duy nhất là đáp án của yêu cầu đề bài. Lưu ý, đáp án là kết quả sau khi đã chia lấy dư cho $10^9 + 7$.

Ví dụ 1 – input

2 2

Ví dụ 1 – output

0

Ví dụ 2 – input

2 1000

Ví dụ 2 – output

1994004

Ví dụ 3 – input

1 1000

Ví dụ 3 – output

2000

Lưu ý nhỏ: đề ghi $K < N$ nhưng ví dụ 1 lại có $K = N = 2$; trong bộ test chính thức thì luôn có $K < N$. Các lời giải bên dưới vẫn đúng khi $K = N$.

Giải thích ví dụ 3: $K = 1$ thì chọn ô nào cũng được, bảng $2 \times 1000$ có $2000$ ô. Ví dụ 1: bảng $2 \times 2$ thì 4 ô đôi một chung đỉnh, không thể chọn 2 ô → $0$ cách.

Lời mở đầu

Đây là bài thứ 4 của đề Tin học trẻ bảng C2 Cần Thơ 2024 – một bài quy hoạch động đếm rất "sạch". Mình sẽ đi theo đúng lộ trình của chương: vét cạn mọi cách chọn để ăn 40% điểm, rồi tìm ra quan sát quan trọng để viết công thức quy hoạch động $f[i][j]$, và cuối cùng biến công thức đó thành một tổ hợp $O(N)$ đúng với mọi $K$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testCách 1Vét cạn 40%Ý tưởngBảng f[i][j]Cách 2QHĐ O(NK)Cách 3Tổ hợp O(N)

Bộ testBộ test chính thức có gì?

Test	$K$	$N$	Số test đáp án 0
1–40	1 … 9	3 … 10	16
41–60	13 … 47	109 … 1.000	0
61–100	11 … 50	10.000 … 100.000	0

Bộ test chia đúng theo ràng buộc của đề: 40 test đầu có $N \le 10$ (đủ mọi cặp $1 \le K < N \le 10$), 20 test kế có $N \le 1000$, 40 test cuối có $N$ = $10^4$ hoặc $10^5$. Có 20 test đáp án bằng 0 (ví dụ $K = 3, N = 4$) – sau khi hiểu ý tưởng các bạn sẽ thấy ngay vì sao. Một điểm đáng chú ý: tuy đề cho $K$ tới gần $10^5$, nhưng trong mọi test $K \le 50$.

Phần	Điều kiện	Test	Cách 1 (vét cạn)	Cách 2 (QHĐ bảng)	Cách 3 (tổ hợp)
Ràng buộc 1	$N \le 10$	1–40	qua	qua	qua
Ràng buộc 2	$N \le 10^3$	41–60	không chạy nổi	qua	qua
Còn lại	$N \le 10^5$	61–100	không chạy nổi	qua (nhờ $K \le 50$)	qua

Cách 1Vét cạn mọi tập ô (ràng buộc 1)

Bảng có $2N$ ô. Đánh số ô hàng trên cột $c$ là bit $c$, ô hàng dưới cột $c$ là bit $N + c$ (cột đánh số từ 0). Mỗi số mask từ $0$ đến $2^{2N} - 1$ là một tập ô. Ta chỉ giữ các mask có đúng $K$ bit 1, rồi kiểm tra điều kiện "không chung đỉnh". Nhìn kỹ hình đề bài thì hai ô chung đỉnh chỉ có thể là:

• hai ô cùng một cột (chung cạnh ngang), hoặc
• hai ô ở hai cột kề nhau – kể cả khác hàng, vì khi đó chúng chạm nhau ở góc.

Hai ô cách nhau từ 2 cột trở lên thì không bao giờ chạm nhau. Vậy chỉ cần kiểm tra từng cột và từng cặp cột kề nhau.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi mask 2N bit, giữ mask có đúng K bit 1 rồi kiểm tra từng cột.

Dữ liệu vào (stdin) – sửa thoải mái2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hình vẽ bảng 2 × N: hàng trên là các bit 0..N−1, hàng dưới là các bit N..2N−1.

Không gian$O(1)$

Thời gian$O(2^{2N} \cdot N)$

Kết quả chạy thật: bản C++ đúng 40/100 test – trọn ràng buộc 1, chậm nhất 0,009 giây. Từ test 41 trở đi $N \ge 109$ thì $2^{2N}$ là con số khổng lồ (và cũng không còn vừa trong kiểu int), cách này không chạy nổi. Bản Python cũng qua cả 40 test đầu, chậm nhất 0,35 giây.

Ý tưởng QHĐMỗi cột chọn tối đa 1 ô, 2 cột kề nhau không cùng chọn

Từ nhận xét ở cách 1, bài toán trở thành: chọn ra $K$ cột trong $N$ cột sao cho không có 2 cột kề nhau, rồi ở mỗi cột được chọn quyết định lấy ô trên hay ô dưới (2 cách). Giờ ta đếm bằng quy hoạch động theo từng cột từ trái sang phải.

Gọi $f[i][j]$ = số cách chọn $j$ ô trong $i$ cột đầu tiên thoả điều kiện. Xét cột cuối cùng – cột $i$:

1. Cột $i$ để trống: $j$ ô đều nằm trong $i - 1$ cột đầu → $f[i-1][j]$ cách.
2. Cột $i$ có 1 ô (trên hoặc dưới – 2 cách): khi đó cột $i - 1$ bắt buộc trống, $j - 1$ ô còn lại nằm trong $i - 2$ cột đầu → $2 \cdot f[i-2][j-1]$ cách.

Công thức truy hồi

$$f[i][j] = f[i-1][j] + 2 \cdot f[i-2][j-1]$$ Cơ sở: $f[i][0] = 1$ (không chọn gì), $f[0][j] = 0$ với $j > 0$. Với $i = 1$ thì "$f[-1][j-1]$" hiểu là $1$ khi $j = 1$ (bên trái cột 1 không còn gì). Đáp án là $f[N][K]$.

Em nhập $K$, $N$ rồi bấm Tiếp để xem bảng $f$ được điền từng ô. Ô vàng đang tính, hai ô xanh tím là $f[i-1][j]$ và $f[i-2][j-1]$; hàng dưới vẽ bảng $2 \times N$ để thấy cột $i$ (vàng) và cột $i-1$ phải để trống (gạch):

ô đang tínhf[i−1][j] và f[i−2][j−1]kết quảđáp án f[N][K]

K N

Ví dụ nhanh:

Cách 2Quy hoạch động bảng $f[i][j]$ – $O(N \cdot K)$

Cài đặt đúng công thức trên. Thêm một nhận xét để thoát sớm: $K$ cột không kề nhau thì cần ít nhất $2K - 1$ cột (chọn – trống – chọn – … – chọn), nên nếu $2K - 1 > N$ đáp án chắc chắn là $0$. Đây chính là 20 test có đáp án 0 trong bộ test.

C++▶ Chạy tay từng dòng codeCách 2: điền bảng f[i][j] = f[i−1][j] + 2·f[i−2][j−1].

Dữ liệu vào (stdin) – sửa thoải mái2 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ô vàng là f[i][j] đang tính, hai ô xanh tím là f[i−1][j] (cột i trống) và f[i−2][j−1] (cột i có ô).

1. Mọi phép cộng đều lấy % MOD ngay: $f[i-1][j]$ $+ 2 f[i-2][j-1] < 3 \cdot 10^9$ $+ 21$ vẫn vừa long long.
2. Bảng có $(N + 1)(K + 1)$ ô. Với bộ test thật ($K \le 50$) bảng chỉ khoảng $10^5 \times 51$ số long long ≈ 41 MB và $5 \cdot 10^6$ phép tính – rất nhẹ.
3. Nhưng nếu đúng như giới hạn đề ($K$ tới khoảng $5 \cdot 10^4$ mà đáp án vẫn khác 0) thì bảng có tới $5 \cdot 10^9$ ô – không đủ bộ nhớ và thời gian. Ta cần làm tốt hơn: cách 3.

Không gian$O(N \cdot K)$

Thời gian$O(N \cdot K)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,054 giây (vì bộ test chỉ có $K \le 50$). Bản Python cùng thuật toán được 91/100 test: 9 test có $N = 10^5$ và $K$ khoảng 35–50 cần tới $5 \cdot 10^6$ phép tính, Python chạy 1,0–1,5 giây nên quá thời gian – các bạn học Python dùng cách 3 nhé.

Cách 3Đếm trực tiếp bằng tổ hợp – $O(N)$ với mọi $K$

Bài toán "chọn $K$ cột đôi một không kề nhau trong $N$ cột" có lời giải đẹp: giữa 2 cột được chọn liên tiếp phải có ít nhất 1 cột trống. Ta "rút" bớt 1 cột trống ngay sau mỗi cột được chọn (trừ cột cuối) – tổng cộng rút $K - 1$ cột. Khi đó ta còn $N - K + 1$ cột và chỉ cần chọn $K$ cột bất kỳ trong đó; ngược lại, từ một cách chọn $K$ cột bất kỳ trong $N - K + 1$ cột, chèn lại 1 cột trống sau mỗi cột được chọn (trừ cột cuối) là được một cách hợp lệ. Hai bên tương ứng 1–1, nên:

Công thức đóng

$$\text{Đáp án} = C_{N-K+1}^{K} \cdot 2^K \pmod{10^9 + 7}$$ Kiểm tra ví dụ 2: $K = 2, N = 1000$: $C_{999}^{2} \cdot 4$ $= 498\,501 \cdot 4$ $= 1\,994\,004$ ✓. Ví dụ 1: $C_1^2 = 0$ ✓.

Muốn tính $C_n^k = \dfrac{n!}{k!\,(n-k)!}$ theo modulo số nguyên tố $p = 10^9 + 7$, ta không chia trực tiếp được mà nhân với nghịch đảo modulo: theo định lý Fermat nhỏ $a^{-1} \equiv a^{p-2} \pmod p$, tính bằng lũy thừa nhanh. Mình tính sẵn mảng giai thừa fact, nghịch đảo inv[N] = fact[N]^{p-2}, rồi lùi dần inv[i-1] = inv[i] · i.

C++▶ Chạy tay từng dòng codeCách 3: đáp án = C(N − K + 1, K) × 2^K, tính tổ hợp bằng giai thừa và nghịch đảo modulo.

Dữ liệu vào (stdin) – sửa thoải mái2 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mình gộp vòng while của lũy thừa nhanh thành 1 bước để khung chạy tay không quá dài.

Không gian$O(N)$

Thời gian$O(N + \log p)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,006 giây; bản Python (chỉ cần nhân $K$ số) cũng 100/100, chậm nhất 0,021 giây.

Ghi chú của mình: cách 1 (vét cạn) được 40/100 test – đúng ràng buộc 1; cách 2 (QHĐ bảng $O(NK)$) được 100/100 trên bộ test này vì mọi test đều có $K \le 50$, nhưng về lý thuyết sẽ quá thời gian / bộ nhớ nếu $K$ lớn; cách 3 (tổ hợp + nghịch đảo modulo) 100/100, chậm nhất 0,006 giây và đúng với mọi $K$. Công thức QHĐ ở cách 2 chính là "cầu nối" giúp mình đoán và kiểm chứng công thức tổ hợp ở cách 3.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇