Quy hoạch động chữ số
Đếm các số từ 1 đến N không chứa chữ số 4. Với N = 106 thì duyệt từng số là xong. Với N = 1018, duyệt từng số cần ước lượng hàng trăm năm. Quy hoạch động chữ số giải bài này bằng vài nghìn phép tính, vì nó không xét từng số mà xét từng chữ số: N có 19 chữ số, mỗi chữ số có 10 lựa chọn.
Các bạn cần nắm vững bài Quy tắc cộng, quy tắc nhân và bài Dãy truy hồi trước khi học bài này.
Chạy tay: các số từ 0 đến 345 không chứa chữ số 4
Phần tiêu đề “Chạy tay: các số từ 0 đến 345 không chứa chữ số 4”Viết mọi số thành 3 chữ số (thêm 0 ở đầu: 7 thành 007). Đi từ chữ số trái nhất:
- Chữ số đầu nhỏ hơn 3 (0, 1 hoặc 2): số chắc chắn nhỏ hơn 345, hai chữ số sau tự do, mỗi chữ số có 9 lựa chọn (trừ 4). Có 3 × 9 × 9 = 243 số.
- Chữ số đầu bằng 3: số vẫn đang bám sát 345, chữ số thứ hai không được vượt quá 4.
- Chữ số thứ hai nhỏ hơn 4 (0, 1, 2, 3): chữ số cuối tự do, có 4 × 9 = 36 số.
- Chữ số thứ hai bằng 4: bị cấm, dừng.
Tổng 243 + 36 = 279 số từ 0 đến 345, bỏ số 0 còn 278 số từ 1 đến 345.
Ý quan trọng nhất là trạng thái chặt: khi các chữ số đã chọn bằng đúng các chữ số đầu của N, chữ số tiếp theo không được vượt quá chữ số tương ứng của N. Chỉ cần chọn một chữ số nhỏ hơn là hết chặt, các chữ số sau tự do từ 0 đến 9.
Mẫu chương trình
Phần tiêu đề “Mẫu chương trình”Gọi f(vị trí, chặt) là số cách chọn các chữ số từ vị trí đó đến hết. Ở mỗi vị trí, thử mọi chữ số d được phép; chữ số tiếp theo vẫn chặt khi bây giờ đang chặt và d bằng đúng chữ số của N.
from functools import lru_cache
def dem(N): """Số các số từ 0 đến N không chứa chữ số 4.""" s = str(N)
@lru_cache(maxsize=None) def f(vi_tri, chat): if vi_tri == len(s): return 1 # đã chọn xong một số hợp lệ gioi_han = int(s[vi_tri]) if chat else 9 tong = 0 for d in range(gioi_han + 1): if d == 4: continue tong += f(vi_tri + 1, chat and d == gioi_han) return tong
return f(0, True)
print(dem(345) - 1) # 278 (bỏ số 0)print(dem(10 ** 18) - 1) # 150094635296999121#include <iostream>#include <string>#include <cstring>using namespace std;
string s;long long nho[20][2];
long long f(int viTri, int chat) { if (viTri == (int)s.size()) return 1; long long &kq = nho[viTri][chat]; if (kq != -1) return kq; kq = 0; int gioiHan = chat ? s[viTri] - '0' : 9; for (int d = 0; d <= gioiHan; d++) { if (d == 4) continue; kq += f(viTri + 1, chat && d == gioiHan); } return kq;}
long long dem(long long N) { s = to_string(N); memset(nho, -1, sizeof nho); return f(0, 1);}
int main() { cout << dem(345) - 1 << endl; // 278 cout << dem(1000000000000000000LL) - 1 << endl; // 150094635296999121 return 0;}Có khoảng 19 × 2 trạng thái, mỗi trạng thái thử 10 chữ số: vài trăm phép tính.
Đếm trong đoạn từ L đến R: lấy dem(R) - dem(L - 1). Đây là lý do luôn viết hàm đếm từ 0 đến N.
Thêm thông tin vào trạng thái
Phần tiêu đề “Thêm thông tin vào trạng thái”Điều kiện phức tạp hơn thì trạng thái cần nhớ thêm những gì cần biết về các chữ số đã chọn. Ví dụ đếm số có tổng chữ số chia hết cho k: chỉ cần nhớ tổng các chữ số đã chọn chia k dư bao nhiêu, không cần nhớ cả tổng.
f(vị trí, dư, chặt): chọn chữ số d thì dư mới là (dư + d) % k. Khi chọn xong mọi chữ số, trả về 1 nếu dư = 0, ngược lại trả về 0. Số trạng thái là 19 × k × 2.
Một vài thông tin hay gặp:
| Điều kiện | Cần nhớ thêm |
|---|---|
| tổng chữ số chia hết cho k | tổng % k |
| bản thân số chia hết cho m | số đã chọn % m (thêm chữ số d: (dư × 10 + d) % m) |
| hai chữ số kề nhau khác nhau | chữ số vừa chọn |
| các chữ số đôi một khác nhau | tập các chữ số đã dùng (một số 10 bit) |
| có đúng k chữ số khác 0 | số chữ số khác 0 đã chọn |
Chỉ nhớ đúng những gì cần. Trạng thái càng ít, chương trình càng nhanh.
Số 0 đứng đầu
Phần tiêu đề “Số 0 đứng đầu”Viết 7 thành 007 thì các chữ số 0 ở đầu không phải chữ số thật. Với điều kiện “không chứa chữ số 4” thì không sao, nhưng với điều kiện “hai chữ số kề nhau khác nhau” thì 007 bị coi là có hai số 0 kề nhau, sai. Khi đó thêm trạng thái đã bắt đầu (đã chọn chữ số khác 0 nào chưa): chừng nào chưa bắt đầu, chữ số 0 được bỏ qua, không tính vào điều kiện.
Tính tổng thay vì đếm
Phần tiêu đề “Tính tổng thay vì đếm”Muốn tính tổng (ví dụ tổng chữ số của mọi số từ 1 đến N), cho hàm trả về hai giá trị: số cách chọn phần còn lại, và tổng cần tính trên các cách đó. Chọn chữ số d rồi gọi phần sau được (đếm, tổng) thì phần đóng góp là (đếm, tổng + d × đếm): chữ số d có mặt trong tất cả “đếm” số.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Mẫu cơ bản
Phần tiêu đề “Nhóm 1. Mẫu cơ bản”Bài 1. Không chứa chữ số 4
Phần tiêu đề “Bài 1. Không chứa chữ số 4”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N không chứa chữ số 4?
Ví dụ: nhập 345 thì in ra 278.
Kiểm tra: nhập 1000000000000000000.
Bài 2. Tổng chữ số chia hết cho k
Phần tiêu đề “Bài 2. Tổng chữ số chia hết cho k”Nhập L, R, k (1 ≤ L ≤ R ≤ 1018, 1 ≤ k ≤ 100). Có bao nhiêu số từ L đến R có tổng các chữ số chia hết cho k?
Ví dụ: nhập 1 100 3 thì in ra 33.
Kiểm tra: nhập 1 1000000000000000000 7.
Bài 3. Tổng chữ số bằng S
Phần tiêu đề “Bài 3. Tổng chữ số bằng S”Nhập N, S (1 ≤ N ≤ 1018, 1 ≤ S ≤ 200). Có bao nhiêu số từ 1 đến N có tổng các chữ số đúng bằng S?
Ví dụ: nhập 100 10 thì in ra 9.
Kiểm tra: nhập 1000000000000000000 81.
Bài 4. Đếm chữ số 1
Phần tiêu đề “Bài 4. Đếm chữ số 1”Viết các số từ 1 đến N liên tiếp nhau. Chữ số 1 xuất hiện tất cả bao nhiêu lần? Nhập N (1 ≤ N ≤ 1018).
Ví dụ: nhập 13 thì in ra 6.
Kiểm tra: nhập 1000000000000000000.
Bài 5. Tổng các chữ số
Phần tiêu đề “Bài 5. Tổng các chữ số”Nhập N (1 ≤ N ≤ 1018). Tính tổng các chữ số của mọi số từ 1 đến N, chia lấy dư cho 109 + 7.
Ví dụ: nhập 12 thì in ra 51.
Kiểm tra: nhập 1000000000000000000.
Nhóm 2. Nhớ thêm chữ số vừa chọn
Phần tiêu đề “Nhóm 2. Nhớ thêm chữ số vừa chọn”Bài 6. Hai chữ số kề nhau khác nhau
Phần tiêu đề “Bài 6. Hai chữ số kề nhau khác nhau”Nhập L, R (1 ≤ L ≤ R ≤ 1018). Có bao nhiêu số từ L đến R mà không có hai chữ số kề nhau nào bằng nhau?
Ví dụ: nhập 1 100 thì in ra 90.
Kiểm tra: nhập 1 1000000000000000000.
Bài 7. Chữ số không giảm
Phần tiêu đề “Bài 7. Chữ số không giảm”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N mà các chữ số không giảm khi đọc từ trái sang phải (ví dụ 1129, 7, 3389)?
Ví dụ: nhập 100 thì in ra 54.
Kiểm tra: nhập 1000000000000000000.
Bài 8. Hai điều kiện chia hết
Phần tiêu đề “Bài 8. Hai điều kiện chia hết”Nhập N, a, b (1 ≤ N ≤ 1018, 1 ≤ a, b ≤ 60). Có bao nhiêu số từ 1 đến N vừa chia hết cho a, vừa có tổng chữ số chia hết cho b?
Ví dụ: nhập 100 5 2 thì in ra 9.
Kiểm tra: nhập 1000000000000000000 7 9.
Bài 9. Đúng k chữ số khác 0
Phần tiêu đề “Bài 9. Đúng k chữ số khác 0”Nhập N và k (N là số nguyên dương có không quá 100 chữ số, 1 ≤ k ≤ 3). Có bao nhiêu số từ 1 đến N có đúng k chữ số khác 0?
Ví dụ: nhập 100 1 thì in ra 19.
Kiểm tra: nhập 31415926535897932384626433832795028841971693993751 2.
Bài 10. Có chứa chữ số 0
Phần tiêu đề “Bài 10. Có chứa chữ số 0”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N có chứa ít nhất một chữ số 0?
Ví dụ: nhập 100 thì in ra 10.
Kiểm tra: nhập 1000000000000000000.
Nhóm 3. Biến thể
Phần tiêu đề “Nhóm 3. Biến thể”Bài 11. Cân bằng chẵn lẻ
Phần tiêu đề “Bài 11. Cân bằng chẵn lẻ”Đánh số vị trí các chữ số từ phải sang trái bắt đầu từ 1 (chữ số hàng đơn vị ở vị trí 1). Số cân bằng là số có tổng các chữ số ở vị trí lẻ bằng tổng các chữ số ở vị trí chẵn (ví dụ 121: 1 + 1 = 2). Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số cân bằng từ 1 đến N?
Ví dụ: nhập 100 thì in ra 9.
Kiểm tra: nhập 1000000000000000000.
Bài 12. Số thứ k không chứa chữ số 4
Phần tiêu đề “Bài 12. Số thứ k không chứa chữ số 4”Xếp các số nguyên dương không chứa chữ số 4 theo thứ tự tăng dần: 1, 2, 3, 5, 6, … Nhập k (1 ≤ k ≤ 1017). In ra số thứ k.
Ví dụ: nhập 4 thì in ra 5.
Kiểm tra: nhập 100000000000000000.
Bài 13. Nhiều chữ số 3 hơn chữ số 5
Phần tiêu đề “Bài 13. Nhiều chữ số 3 hơn chữ số 5”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N mà chữ số 3 xuất hiện nhiều hơn chữ số 5?
Ví dụ: nhập 40 thì in ra 12.
Kiểm tra: nhập 1000000000000000000.
Bài 14. Đúng k bit 1
Phần tiêu đề “Bài 14. Đúng k bit 1”Nhập N, k (1 ≤ N ≤ 1018, 1 ≤ k ≤ 60). Có bao nhiêu số từ 1 đến N mà khi viết trong hệ nhị phân có đúng k chữ số 1?
Ví dụ: nhập 10 2 thì in ra 5.
Kiểm tra: nhập 1000000000000000000 30.
Bài 15. Tổng các số thỏa mãn
Phần tiêu đề “Bài 15. Tổng các số thỏa mãn”Nhập N (1 ≤ N ≤ 1018). Tính tổng các số từ 1 đến N có tổng chữ số chia hết cho 10, chia lấy dư cho 109 + 7.
Ví dụ: nhập 100 thì in ra 495.
Kiểm tra: nhập 1000000000000000000.
Nhóm 4. Trạng thái phức tạp hơn
Phần tiêu đề “Nhóm 4. Trạng thái phức tạp hơn”Bài 16. Tổng chữ số là số nguyên tố
Phần tiêu đề “Bài 16. Tổng chữ số là số nguyên tố”Nhập L, R (1 ≤ L ≤ R ≤ 1018). Có bao nhiêu số từ L đến R có tổng các chữ số là số nguyên tố?
Ví dụ: nhập 1 20 thì in ra 9.
Kiểm tra: nhập 1 1000000000000000000.
Bài 17. Các chữ số đôi một khác nhau
Phần tiêu đề “Bài 17. Các chữ số đôi một khác nhau”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N có các chữ số đôi một khác nhau (ví dụ 1023 được, 1123 không được)?
Ví dụ: nhập 100 thì in ra 90.
Kiểm tra: nhập 1000000000000000000.
Bài 18. Mỗi chữ số xuất hiện chẵn lần
Phần tiêu đề “Bài 18. Mỗi chữ số xuất hiện chẵn lần”Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N mà mỗi chữ số có mặt trong nó đều xuất hiện một số chẵn lần (ví dụ 1221, 3030, 77)?
Ví dụ: nhập 100 thì in ra 9.
Kiểm tra: nhập 1000000000000000000.
Bài 19. Số bậc thang
Phần tiêu đề “Bài 19. Số bậc thang”Số bậc thang là số mà hai chữ số kề nhau luôn hơn kém nhau đúng 1 (ví dụ 7, 10, 3454, 98789). Nhập L, R (1 ≤ L ≤ R, mỗi số có không quá 100 chữ số). Có bao nhiêu số bậc thang từ L đến R? In ra kết quả chia lấy dư cho 109 + 7.
Ví dụ: nhập 1 100 thì in ra 26.
Kiểm tra: nhập 1 10000000000000000000000000000000000000000000000000.
Bài 20. Không chứa “13”
Phần tiêu đề “Bài 20. Không chứa “13””Nhập N (1 ≤ N ≤ 1018). Có bao nhiêu số từ 1 đến N mà khi viết ra không có chữ số 1 đứng ngay trước chữ số 3 (ví dụ 135, 2130 bị loại; 31, 103 được)?
Ví dụ: nhập 200 thì in ra 188.
Kiểm tra: nhập 1000000000000000000.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.