DP chữ số (Digit DP)

DP chữ số (Digit DP) là kỹ thuật quy hoạch động dùng để đếm số lượng số nguyên trong đoạn $[L,R]$ thỏa mãn một tính chất nào đó liên quan đến các chữ số của chúng (ví dụ: tổng chữ số chia hết cho $K$, không có hai chữ số giống nhau đứng cạnh nhau, chứa đúng $t$ chữ số $7$...).

Điểm mạnh: thay vì duyệt trâu từng số trong $[L,R]$ với chi phí $O(R-L)$ (vô vọng khi $R$ tới ${10}^{18}$), Digit DP xây số theo từng chữ số từ trái sang phải và đếm gộp, đạt độ phức tạp chỉ phụ thuộc vào số chữ số — khoảng $O(18\times |\text{state}|\times 10)$, tức gần như tức thời.

Ý tưởng / Trực giác

1. Quy bài toán về tiền tố: $f(N)$

Đếm trên $[L,R]$ khó vì có hai biên. Ta tách đôi bằng nguyên lý bù trừ:

$$\text{Đáp án trên }[L,R]=f(R)-f(L-1)$$

trong đó $f(N)$ = số lượng số trong $[0,N]$ thỏa điều kiện. Giờ chỉ còn một biên trên duy nhất là $N$ — dễ xử lý hơn nhiều.

2. Vì sao xây theo chữ số lại đúng?

Gọi $N$ có các chữ số $d_0{d}_1\dots d_{m-1}$ (cao → thấp). Xét tập tất cả số có đúng $m$ chữ số (cho phép số 0 đứng đầu) trong khoảng $[0,N]$. Mọi số $x\le N$ rơi vào đúng một trong hai loại tại vị trí chữ số đầu tiên mà nó khác $N$:

• Bám sát biên (tight): mọi chữ số từ đầu đến pos đều bằng $N$. Lúc này chữ số tại pos không được vượt $d_{pos}$, vì vượt là lớn hơn $N$.
• Đã thoát biên (free): ở một vị trí nào đó trước pos, ta đã chọn chữ số nhỏ hơn chữ số tương ứng của $N$. Khi đó phần đuôi còn lại được chọn tự do từ 0 đến 9, chắc chắn vẫn $\le N$.

Cờ tight chính là thứ phân biệt hai loại này. Nhận xét then chốt: khi đã free (tight = false), kết quả đếm cho phần đuôi không còn phụ thuộc vào $N$ nữa, chỉ phụ thuộc vào trạng thái bài toán. Đó là lý do ta có thể ghi nhớ (memo) các trạng thái free và tái sử dụng — nguồn gốc của tốc độ.

3. Trạng thái cần mang theo

Khi xây dở dang một số, ta chỉ cần lưu đủ thông tin để biết phần đuôi nào hợp lệ:

Vì state thường nhỏ và pos $\le 19$, tổng số trạng thái rất ít → DP chạy nhanh.

Ví dụ chạy tay

Bài: đếm số trong $[0,21]$ có tổng chữ số bằng $S=3$. Đáp án mong đợi: $3,12,21,30$? — nhưng $30>21$, nên chỉ có $3,12,21$ → 3 số.

Ta gọi $f(21)$. Chuỗi digits = "21", $m=2$. Trạng thái dp(pos, sum, tight) = số cách điền các vị trí từ pos để tổng cuối đạt $S$.

Cây đệ quy (chỉ vẽ nhánh tight, ghi limit = chữ số tối đa được chọn):

dp(0, sum=0, tight=1)   digits[0]=2 -> limit=2
│
├─ d=0 -> dp(1, sum=0, tight=0)   free, limit=9   cần chữ số = 3 -> CHỌN d=3 (1 cách)   => "03" = 3   ✔
│
├─ d=1 -> dp(1, sum=1, tight=0)   free, limit=9   cần chữ số = 2 -> CHỌN d=2 (1 cách)   => "12"      ✔
│
└─ d=2 -> dp(1, sum=2, tight=1)   digits[1]=1 -> limit=1
          ├─ d=0 -> sum=2 != 3   ✗
          └─ d=1 -> sum=3 == 3   ✔   => "21"

Bảng đánh dấu ô đang xét tại pos = 1 (hàng = sum tích lũy tới giờ, cột = giá trị trả về):

Cộng lại: $1+1+1=3$. Khớp đáp án. Để ra kết quả trên $[L,R]$ thật, ta lấy $f(R)-f(L-1)$.

Cài đặt

Đếm số trong $[0,N]$ có tổng chữ số bằng $S$ (mẫu cơ bản, có tight):

#include <bits/stdc++.h>
using namespace std;

int S;
string digits;
long long memo[20][200][2];   // [pos][sum][tight]

// Số cách điền từ vị trí pos sao cho TỔNG CUỐI = S,
// với sum = tổng đã tích lũy, tight = còn bám biên trên không.
long long dp(int pos, int sum, bool tight) {
    if (sum > S) return 0;                      // cắt nhánh: đã vượt
    if (pos == (int)digits.size())              // điền xong cả số
        return (sum == S) ? 1 : 0;

    long long &ret = memo[pos][sum][tight];
    if (ret != -1) return ret;                  // đã tính -> dùng lại

    int limit = tight ? (digits[pos] - '0') : 9; // tight: tối đa = digits[pos]
    ret = 0;
    for (int d = 0; d <= limit; d++) {
        // chỉ còn tight nếu trước đó tight VÀ chọn đúng cận d == limit
        ret += dp(pos + 1, sum + d, tight && (d == limit));
    }
    return ret;
}

long long f(long long N) {
    if (N < 0) return 0;                         // f(-1) = 0
    digits = to_string(N);
    memset(memo, -1, sizeof(memo));              // BẮT BUỘC xóa trước mỗi f()
    return dp(0, 0, /*tight=*/true);             // bắt đầu luôn bám biên
}

int main() {
    long long L, R; int s;
    cin >> L >> R >> s; S = s;
    cout << f(R) - f(L - 1) << "\n";
}

Mẫu tổng quát có started (xử lý số 0 đứng đầu)

Khi điều kiện đếm phụ thuộc độ dài thực của số (ví dụ "số có đúng $k$ chữ số khác 0"), phải phân biệt 7 với 007. Thêm cờ started: chừng nào chưa điền chữ số khác 0 thì không cập nhật trạng thái.

long long dp(int pos, int state, bool tight, bool started) {
    if (pos == (int)digits.size())
        return started ? (state == /*target*/0) : 0; // số 0 thường tính riêng

    long long &ret = memo[pos][state][tight][started];
    if (ret != -1) return ret;

    int limit = tight ? (digits[pos] - '0') : 9;
    ret = 0;
    for (int d = 0; d <= limit; d++) {
        bool nStarted = started || (d != 0);
        // khi chưa started và d==0: vẫn là "số 0 đệm", KHÔNG đổi state
        int nState = nStarted ? transition(state, d) : state;
        ret += dp(pos + 1, nState, tight && (d == limit), nStarted);
    }
    return ret;
}

Độ phức tạp

Gọi $m=\lfloor {\log }_{10}N\rfloor +1$ là số chữ số ($\le 19$ với $N\le {10}^{18}$) và $|state|$ là số trạng thái riêng.

• Thời gian: $O(m\times |state|\times 2\times 10)$. Mỗi bộ (pos, state, tight) được tính đúng một lần nhờ memo (đây là điểm mấu chốt), mỗi lần duyệt $\le 10$ giá trị chữ số. Với $m=19$, hằng số $|state|$ nhỏ → vài chục nghìn phép tính, gần như tức thời, kể cả khi có $T$ truy vấn.
• Bộ nhớ: $O(m\times |state|\times 2)$ cho mảng memo. Chiều tight thực ra chỉ cần cho nhánh bám biên; nhiều người bỏ luôn tight khỏi memo và chỉ memo nhánh free để tiết kiệm.

Lý do nhanh hơn duyệt trâu: duyệt trâu là $O(R-L)$ (có thể ${10}^{18}$), còn Digit DP gộp toàn bộ phần đuôi "free" thành một lần tính rồi tái sử dụng.

⚠️ Lỗi thường gặp

• Không xóa memo giữa f(R) và f(L-1). Mảng memo chứa kết quả cho nhánh free — vốn không phụ thuộc $N$ nên dùng chung được — nhưng nếu bạn (lỡ) memo cả ô có tight = true thì giá trị digits đã đổi sang số khác, kết quả sai. An toàn nhất: memset(memo, -1, ...) ở đầu mỗi f(N). Triệu chứng: test đơn lẻ đúng, nhiều truy vấn liên tiếp ra sai.
• Memo nhầm theo tight. Khi tight = true, kết quả phụ thuộc vào các chữ số của $N$ tại vị trí đó, không được ghi nhớ và tái dùng cho $N$ khác. Chỉ ô tight = false mới an toàn để cache. Nếu vẫn để chung mảng, ít nhất phải reset mỗi f().
• Quên cờ started khi điều kiện phụ thuộc độ dài số. Đếm "số có tổng chữ số = 0" mà không có started sẽ vô tình đếm vô số số 0 đệm (00, 000...) là hợp lệ. Triệu chứng: kết quả lớn bất thường, hoặc đếm dư số 0.
• Tràn số. Đáp số có thể vượt int (đếm tới ${10}^{18}$ số). Dùng long long cho cả memo lẫn biến cộng dồn; nếu đề yêu cầu lấy dư thì % MOD sau mỗi lần cộng, và cẩn thận modulo âm khi tính $f(R)-f(L-1)$: viết ((f(R) - f(L-1)) % MOD + MOD) % MOD.
• Quên f(L - 1) khi $L=0$. Phải để f(-1) = 0 (thêm if (N < 0) return 0;), nếu không to_string(-1) sẽ tạo chuỗi "-1" và sập logic.
• Sai cập nhật tight. Công thức đúng là newTight = tight && (d == limit). Viết nhầm thành d == 9 hay tight && d <= limit đều làm đếm sai (đếm thiếu hoặc thừa các số bám biên).

Biến thể / Mở rộng

Liên quan: kỹ thuật bù trừ $f(R)-f(L-1)$ ở đây giống ý tưởng tổng tiền tố (prefix sum) trên trục số; phần memo theo trạng thái là tư duy chung của Quy hoạch động.

Bài tập luyện

• Đồng Hồ Đo Quãng Đường (odometers) — (Advanced) Đếm các số "khó đọc" trong đoạn dựa trên hình dạng chữ số — bài nhập môn tight + đếm theo điều kiện chữ số.
• Đếm số theo ràng buộc tần suất chữ số (numcnt) — (Veteran) Trạng thái là tần suất xuất hiện của các chữ số, luyện thiết kế state nhiều chiều.
• Đếm số theo ràng buộc chữ số (digcnt) — (Veteran) Đếm số trong đoạn thỏa ràng buộc trên các chữ số — mẫu Digit DP $f(R)-f(L-1)$ kinh điển có started.
• Khối chữ số modulo (blockmod) — (Veteran) Kết hợp Digit DP với số dư modulo, luyện trạng thái value % K và lấy dư an toàn.
• Xếp Chồng Giấy (pilpaper) — (Veteran) Bài Digit DP nâng cao trộn yếu tố toán học, đòi hỏi định nghĩa trạng thái khéo và xử lý biên cẩn thận.