Số bnum (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng B, C1, C2)

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng B, C1, C2 Độ khó: Khá Quy hoạch động Tổng tập con Tổ hợp

Đề bài

Một số nguyên dương được gọi là số rnum nếu ta chia được các chữ số của nó thành hai nhóm có tổng bằng nhau (mỗi chữ số thuộc đúng một nhóm). Nếu không có cách chia nào như vậy thì số đó gọi là số bnum.

Ví dụ: $28952$ là số rnum vì $8 + 5 = 9 + 2 + 2$ (cùng bằng 13), còn $28951$ là số bnum (tổng các chữ số là 25 – số lẻ – nên không thể chia đôi).

Yêu cầu: đếm số lượng số bnum có không quá $n$ chữ số và mọi chữ số đều nằm trong đoạn $[0, k]$.

Dữ liệu vào: nhiều dòng (không quá 5 dòng), mỗi dòng gồm hai số nguyên $n$ và $k$ ($1 \le n \le 20$, $1 \le k \le 9$). Đọc đến hết dữ liệu.

Kết quả: với mỗi dòng dữ liệu vào, in ra một dòng là số lượng số bnum tương ứng.

Subtask:

Subtask 1 (30%): $k = 1$.
Subtask 2 (30%): $n \le 10$.
Subtask 3 (40%): không có ràng buộc gì thêm.

Giới hạn thời gian 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

1 5
4 3

Ví dụ – output

5
164

Giải thích: với $n = 1, k = 5$: các số $1, 2, 3, 4, 5$ đều chỉ có một chữ số nên không chia được thành hai nhóm bằng nhau → cả 5 số đều là bnum. Với $n = 4, k = 3$ có 164 số bnum (các số từ 1 đến 3333 chỉ gồm chữ số 0..3).

Lời mở đầu

Bài này là sự kết hợp đẹp của ba kiến thức: bài toán tổng tập con (subset sum – kiểm tra một số có phải bnum), quy hoạch động (đếm thay vì duyệt) và tổ hợp (đếm số cách sắp xếp chữ số). Đáp án lớn nhất là 50.000.067.035.394.551.244 – vượt quá cả unsigned long long ($\approx 1{,}8 \cdot 10^{19}$), nên C++ phải dùng số nguyên 128 bit. Mình đi từ vét cạn tới lời giải chạy trong vài phần trăm giây nhé.

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ộ test21 test Ý tưởngtổng tập con Cách 1vét cạn Cách 2QHĐ vị trí Cách 3full Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình có 21 test (giống bộ trên CLUE), mỗi test có từ 1 đến 5 dòng truy vấn. Mình xếp mỗi test vào subtask "nhỏ nhất" mà mọi dòng của nó thoả:

Nhóm	Các test	Số dòng / test	$n$	$k$	Đáp án lớn nhất
Subtask 1	2–7	1 – 5	1 – 20	1 – 1	524.288
Subtask 2	1, 8–13	1 – 5	1 – 10	1 – 9	5.048.078.760
Subtask 3	14–21	1 – 5	3 – 20	1 – 9	50.000.067.035.394.551.244

Test 1 là test đề (thuộc subtask 2 vì có dòng $k = 5$ nhưng $n \le 10$).
Có test chứa 5 dòng giống hệt nhau 20 9 – trường hợp nặng nhất lặp lại 5 lần, rất "ác" với lời giải tính lại từ đầu cho mỗi dòng.
Đáp án của 20 9 là 50.000.067.035.394.551.244 > $2^{64}$.

Kết quả chạy thật của 3 cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 vét cạn	Cách 2 QHĐ theo vị trí	Cách 3 QHĐ theo chữ số
Subtask 1 (30%)	$k = 1$	2–7	qua	qua	qua
Subtask 2 (30%)	$n \le 10$	1, 8–13	3/7 test	qua	qua
Subtask 3 (40%)	không ràng buộc thêm	14–21	0/8 test	7/8 test	qua

Lời giải theo cùng ý tưởng với Cách 3 (duyệt các bộ số lượng chữ số) mình đã nộp thử trên trang chấm chính thức tinhoctre.vn và đạt 100 điểm (AC).

Ý tưởngKiểm tra một số: bài toán tổng tập con

Gọi tổng các chữ số là $s$. Chia được thành hai nhóm bằng nhau ⇔ chọn được một nhóm chữ số có tổng đúng bằng $s / 2$. Vậy:

Nếu $s$ lẻ → chắc chắn là bnum.
Nếu $s$ chẵn → là rnum khi và chỉ khi tổng $s/2$ "đạt được" bởi một nhóm chữ số nào đó.

Tập các tổng đạt được tính dần từng chữ số: ban đầu chỉ có tổng $0$ (nhóm rỗng); thêm chữ số $d$ thì mỗi tổng cũ $x$ sinh thêm tổng $x + d$ (cho $d$ vào nhóm) – tức là tập mới = tập cũ ∪ (tập cũ + d). Lưu tập này bằng một dãy bit (bitset) thì phép trên chỉ là b |= b << d. Tổng lớn nhất là $9 \cdot 20 = 180$ nên bitset<181> là đủ.

Em nhập một số rồi bấm Tiếp để xem tập tổng đạt được lớn dần theo từng chữ số (ô xanh là tổng đạt được):

Số

Ví dụ nhanh:

Hai nhận xét quan trọng cho việc đếm

Thứ tự chữ số không quan trọng: 28952 và 22589 cùng là rnum. Chỉ cần biết mỗi chữ số xuất hiện bao nhiêu lần.
Chữ số 0 không ảnh hưởng gì (cho vào nhóm nào cũng không đổi tổng). Hơn nữa, "số có không quá $n$ chữ số" chính là một xâu đúng $n$ chữ số nếu cho phép số 0 ở đầu (ví dụ với $n = 4$: số 37 viết thành 0037) – trừ xâu toàn số 0 (là số 0, không dương; và nó cũng không phải bnum vì tổng 0 chia đôi được).

Cách 1Vét cạn mọi số

Duyệt mọi xâu $n$ chữ số trong $[0, k]$ – giống như đếm trong hệ cơ số $k + 1$: mảng d là các chữ số, mỗi lần "cộng 1" vào hàng đơn vị, chữ số nào vượt $k$ thì về 0 và nhớ sang hàng kế tiếp. Với mỗi số, tính bitset tổng con rồi kiểm tra như phần ý tưởng.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi số như đếm trong hệ cơ số k + 1, kiểm tra từng số bằng bitset tổng con.

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

Dữ liệu mẫu:

Dòng 4 3 của test đề có 255 số – khá dài, nên dữ liệu mẫu chỉ lấy dòng đầu; em có thể tự nhập thêm.

Vòng while (i < n && d[i] == k) là phép "nhớ": các hàng đang bằng $k$ quay về 0. Nếu nhớ tràn ra ngoài hàng cao nhất ($i = n$) thì đã duyệt hết.
Số đầu tiên được xét là $0\ldots01$ (vì cộng 1 trước khi kiểm tra), nên số 0 không bị đếm.

Có $(k+1)^n - 1$ số, mỗi số tốn $O(n)$ phép bitset. Với $k = 1$, $n = 20$: khoảng $10^6$ số – chạy tốt, nên vét cạn ăn trọn subtask 1. Còn $n = 10, k = 9$ đã là $10^{10}$ số – không thể.

Mẹo cho subtask 1: khi $k = 1$, các chữ số chỉ là 0 và 1, tổng $s$ là số chữ số 1; chia đôi được ⇔ $s$ chẵn. Một nửa số xâu nhị phân độ dài $n$ có số chữ số 1 lẻ, nên đáp án chính là $2^{n-1}$ (ví dụ 20 1 → $524288$).

Không gian$O(n)$

Thời gian$O\left((k+1)^n \cdot n\right)$ mỗi dòng

Kết quả chạy thật: bản C++ đúng 9/21 test, quá thời gian test 8, 10, 12–21; các test đúng chạy lâu nhất 0,253 giây. Bản Python đúng 5/21 test, quá thời gian test 3–6, 8, 10, 12–21; các test đúng chạy lâu nhất 0,361 giây.

Cách 2QHĐ theo từng vị trí, trạng thái là "tập tổng con"

Thay vì duyệt từng số, ta gom các số có cùng tập tổng con lại: sau khi đã chọn $i$ chữ số đầu, điều duy nhất ảnh hưởng tới tương lai là bitset $b$ các tổng đạt được. Gọi cur[b] = số xâu độ dài $i$ có tập tổng con đúng bằng $b$. Thêm chữ số $d \in [0, k]$: nxt[b | (b << d)] += cur[b]. Sau $n$ bước, cộng cur[b] của mọi $b$ là bnum.

Điều bất ngờ là số bitset khác nhau rất ít: mình đếm thử, với $k = 9$, sau 10 bước chỉ có 11.555 trạng thái, sau 20 bước là 44.232 (trong khi có $10^{20}$ xâu!). Lưu bằng unordered_map với khoá là bitset (C++ có sẵn hàm băm cho bitset).

C++▶ Chạy tay từng dòng codeCách 2: QHĐ theo từng vị trí, gom các xâu có cùng tập tổng con.

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

Dữ liệu mẫu:

Mỗi bước "step" gộp cả hai vòng for (mọi trạng thái × mọi chữ số) thành một bước; ở phần cộng đáp án, khung chỉ dừng ở các trạng thái bnum (và vài trạng thái rnum đầu tiên).

Tổng các chữ số chính là tổng con lớn nhất (chọn hết) – tức bit cao nhất của $b$, nên không cần lưu riêng $s$.
Đáp án có thể vượt $2^{64}$ nên đếm bằng unsigned __int128; C++ không in trực tiếp được kiểu này nên mình viết hàm toStr.

Không gian$O(\text{số trạng thái})$ ≈ 44 nghìn bitset

Thời gian$O(n \cdot (k+1) \cdot \text{số trạng thái})$ mỗi dòng

Kết quả chạy thật: bản C++ đúng 20/21 test, quá thời gian test 16; các test đúng chạy lâu nhất 0,519 giây. Bản Python đúng 17/21 test, quá thời gian test 14–16, 21; các test đúng chạy lâu nhất 0,304 giây.

Một dòng 20 9 tốn khoảng 0,6 giây, nên test có 5 dòng 20 9 bị quá thời gian: cách này tính lại từ đầu cho mỗi dòng và phải đi qua cả $20$ bước $\times$ hàng chục nghìn trạng thái $\times$ 10 chữ số.

Cách 3QHĐ theo giá trị chữ số + tổ hợp (full)

Dùng hai nhận xét ở phần ý tưởng: bỏ chữ số 0 ra, chỉ quan tâm $m$ chữ số khác 0.

Gọi $W[k][m]$ = số xâu gồm đúng $m$ chữ số thuộc $1..k$ là bnum. Khi đó $$\text{đáp án}(n, k) = \sum_{m=1}^{n} \binom{n}{m} \cdot W[k][m],$$ vì ta chọn $m$ vị trí trong $n$ vị trí để đặt chữ số khác 0, các vị trí còn lại là 0.
Tính $W$ bằng QHĐ theo giá trị chữ số $d = 1, 2, \dots, 9$: trạng thái là (số chữ số đã dùng $m$, bitset $b$), giá trị là số xâu. Thêm $c$ chữ số $d$ vào một xâu dài $m$: có $\binom{m+c}{c}$ cách chọn vị trí cho chúng trong xâu mới dài $m + c$, còn bitset thì "dịch-hoặc" $c$ lần.
Sau khi xử lí xong chữ số $d$, các trạng thái chỉ dùng chữ số $\le d$ – cộng các trạng thái bnum vào $W[d][m]$. Vậy một lần QHĐ cho $W$ của mọi $k$, sau đó mỗi dòng truy vấn chỉ mất $O(n)$.

C++▶ Chạy tay từng dòng codeCách 3: tính trước W[k][m] bằng QHĐ theo giá trị chữ số, rồi mỗi dòng cộng C(n, m)·W[k][m].

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

Dữ liệu mẫu:

Khung chạy tay chỉ tính các cột m ≤ n lớn nhất và các chữ số d ≤ k lớn nhất trong dữ liệu em nhập (bản C++ tính đủ tới 20 và 9 – kết quả các dòng nhập vẫn y hệt).

C[m + c][c]: số cách xen $c$ chữ số $d$ giống nhau vào xâu cũ để được xâu dài $m + c$ (thứ tự các chữ số cũ giữ nguyên).
Vòng for c cập nhật b |= b << d sau mỗi lần, nên ở lần lặp thứ $c$, b là bitset sau khi thêm đúng $c$ chữ số $d$.
Kiểm tra lại với test đề: $n = 4, k = 3$ cho 164 ✓.

Không gian$O(20 \cdot \text{số trạng thái})$

Thời giantính trước $\approx 9 \cdot 21 \cdot$ số trạng thái, mỗi dòng $O(n)$

Kết quả chạy thật: bản C++ đúng 21/21 test; các test đúng chạy lâu nhất 0,185 giây. Bản Python đúng 21/21 test; các test đúng chạy lâu nhất 0,644 giây. Full điểm ở cả hai ngôn ngữ – bản Python cũng chạy kịp vì chỉ có khoảng $10^5$ trạng thái (bitset là số nguyên Python, tự lớn tuỳ ý).

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Vét cạn mọi số	C++	9/21	0,253s	Quá thời gian test 8, 10, 12–21
	Python	5/21	0,361s	Quá thời gian test 3–6, 8, 10, 12–21
2. QHĐ theo vị trí, trạng thái = tập tổng con	C++	20/21	0,519s	Quá thời gian test 16
	Python	17/21	0,304s	Quá thời gian test 14–16, 21
3. QHĐ theo giá trị chữ số + tổ hợp	C++	21/21	0,185s	Full điểm
	Python	21/21	0,644s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU trên máy mình, giới hạn 1 giây. Bài học: khi phải đếm trên một tập khổng lồ ($10^{20}$ xâu), hãy hỏi "thông tin nào thật sự cần nhớ?" – ở đây là tập tổng con (Cách 2), rồi tiếp tục "nén" bằng tính chất thứ tự không quan trọng + tổ hợp (Cách 3). Và đừng quên đáp án có thể vượt 64 bit!

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 😇

Lập Trình Thuật Toán