"Hack" Não Số Lớn Với Digit DP!

Xin chào anh em, những chiến binh thuật toán kiên cường!

Đã bao giờ anh em đụng phải bài toán kiểu "Đếm xem từ 1 đến $10^{18}$ (một con số siêu to khổng lồ!) có bao nhiêu số thỏa mãn tính chất 'kỳ cục' nào đó liên quan đến chữ số của nó" chưa?

Phản ứng đầu tiên của nhiều anh em (có cả tôi): "Ối dào, dễ! Quất cái for từ 1 đến $10^{18}$ rồi check thôi!". Khoan... $10^{18}$ á? Cho dù máy anh em có "khủng" cỡ nào, chạy cái vòng lặp đó chắc ngốn... vài triệu năm ánh sáng mất? Lúc đó mình "xanh cỏ" từ lâu mà kết quả chắc vẫn đang chạy. Rõ ràng, cách "ngây thơ" này là tự sát!

Tưởng chừng bế tắc... nhưng không! Luôn có "siêu anh hùng" xuất hiện giải cứu thế giới (thuật toán). Và hôm nay, tôi xin giới thiệu: Digit DP (hay Quy hoạch động chữ số)!

Nghe tên có vẻ "nguy hiểm" nhỉ? Nhưng đừng xoắn, thực ra đây là một kỹ thuật DP khá "hiền", dễ thương mà lại siêu lợi hại.

Vậy Digit DP là gì mà "kinh" thế? Nói đơn giản, thay vì đếm từng số như ông bà ta ngày xưa (và chờ đến Tết Congo), Digit DP giúp ta "xây" các số hợp lệ bằng cách ghép từng chữ số lại, như chơi LEGO ấy. Ta sẽ xem xét từng vị trí và quyết định xem nên đặt chữ số nào vào đó.

Tại sao nên "kết thân" với Digit DP?

• Đây là "vũ khí tối thượng" cho các bài toán đếm số với giới hạn "khủng" ($10^{18}$ là chuyện thường) trên VNOI, Codeforces, AtCoder...
• Biến thuật toán "rùa bò" (duyệt trâu $O(N)$) thành "tên lửa" (thường là $O(\log N)$ hoặc $O((\log N)^k)$), cứu tinh cho những bài giới hạn thời gian eo hẹp!

1. Ý Tưởng Cốt Lõi: Nghĩ Theo Từng "Viên Gạch" Chữ Số

Trái tim của Digit DP nằm ở việc thay đổi cách nhìn về các con số.

• Biến Số Thành Chuỗi/Mảng: Quên việc coi số là giá trị toán học đi. Hãy xem nó như một chuỗi các chữ số. Ví dụ, 314 thành ['3', '1', '4']. Điều này cho phép ta "mổ xẻ" từng chữ số một.
• Công Thức "Thần Thánh" Cho Khoảng $[A, B]$: Hầu hết bài toán yêu cầu đếm trong khoảng $[A, B]$. Đừng cố xử lý trực tiếp! Cách thông minh là xây dựng hàm G(X) đếm số lượng số từ $0$ (hoặc $1$) đến $X$ thỏa mãn điều kiện. Khi đó:

  $$\text{Kết quả} = G(B) - G(A-1)$$

  Đúng vậy, chỉ cần gọi hàm $G$ hai lần và trừ! Cẩn thận khi $A=0$ hoặc $A=1$, đảm bảo hàm $G$ xử lý đúng biên dưới.
• "Xây" Số Từng Bước: Với hàm $G(X)$, ta không duyệt từ 1 đến X. Thay vào đó, ta "xây" các số $\le X$ bằng cách chọn từng chữ số, thường từ trái sang phải (từ hàng cao nhất). Tại mỗi vị trí, ta quyết định xem đặt chữ số nào để không vượt quá $X$ và thỏa mãn điều kiện.

2. Giải Mã Trạng Thái DP: Công Thức Bí Truyền

Quy hoạch động sống nhờ việc nhớ kết quả con đã giải. Trong Digit DP, "bài toán con" là việc xác định xem có bao nhiêu cách hoàn thành việc "xây" số từ một vị trí nhất định trở đi, dựa vào những gì đã xây. Ta cần lưu thông tin quan trọng vào trạng thái DP.

Trạng thái DP giống như "bộ nhớ tạm" của thuật toán, chứa thông tin tối thiểu nhưng đủ để quyết định bước tiếp theo. Xác định đúng trạng thái là cực kỳ quan trọng. Vậy, những thành phần "bất hủ" nào thường góp mặt?

• pos (Position - Vị trí):
  • Ý nghĩa: Đang xét chữ số ở vị trí thứ mấy (thường từ trái sang, 0-based).
  • Ví von: Đang xây LEGO đến tầng thứ mấy.
• tight (Constraint/Limit - Ràng buộc):
  • Ý nghĩa: Tham số "ngôi sao", thường là boolean (1/0). Cho biết việc chọn chữ số tiếp theo có bị giới hạn bởi số $X$ gốc không.
  • Giải thích "xoắn não":
    • tight = true (1): Khi tất cả chữ số đã chọn giống hệt phần đầu của $X$. Ví dụ $X=3145$, đã xây "31", xét vị trí 2 (số 4), thì tight vẫn là true. Lúc này chỉ được chọn chữ số từ 0 đến 4. Nếu chọn 5 là "toang" (vì $315x > 3145$). Giống như đi trên dây phải bám sát số $X$!
    • tight = false (0): Ngay khi bạn chọn một chữ số nhỏ hơn chữ số tương ứng của $X$. Ví dụ $X=3145$, ở vị trí 0 chọn '2' (< '3'), thì tight lập tức thành false cho các vị trí sau. Lúc này, bạn đã "nhảy khỏi dây", được tự do chọn bất kỳ chữ số nào từ 0 đến 9, vì số chắc chắn sẽ nhỏ hơn $X$.
• prop (Property - Thuộc tính cần theo dõi):
  • Ý nghĩa: Một hoặc nhiều tham số lưu thông tin liên quan đến điều kiện đề bài (tổng chữ số, số dư, hiệu, số lần xuất hiện...). Giá trị này được cập nhật sau mỗi lần chọn chữ số.
  • Ví dụ:
    • Đếm số có tổng chữ số = S: Cần biến sum.
    • Đếm số lần xuất hiện chữ số d: Cần biến count.
    • Đếm số có hiệu tổng chẵn/lẻ là số nguyên tố: Cần biến diff.
    • Đếm số "đẹp" (số chữ số chẵn = lẻ và chia hết cho k): Cần diff và mod.
• started / isLeadingZero (Cờ xử lý số 0 ở đầu):
  • Ý nghĩa: Biến boolean khác, cực kỳ quan trọng để xử lý đúng số 0 ở đầu. Phân biệt số 0 "đệm" và số 0 có nghĩa.
  • Hoạt động:
    • started = false (0): Đang ở đầu và chưa gặp số khác 0. Nếu chọn 0, started vẫn false. Nếu chọn khác 0, started thành true.
    • started = true (1): Số đã thực sự bắt đầu. Mọi số 0 từ đây đều có nghĩa.
  • Tại sao cần? Nhiều bài có điều kiện khác nhau cho số 0 đứng đầu. Ví dụ, đếm số dương có tổng S (phải loại số 0). Hoặc các chữ số liền kề phải khác nhau ("007" hợp lệ nếu bỏ 0 đầu, không hợp lệ nếu tính cả hai). Cờ started giúp xử lý việc này.

Tại sao chỉ cần những trạng thái này? Khi ở vị trí pos, quyết định chọn chữ số tiếp theo phụ thuộc vào:

1. Giới hạn lựa chọn: Có bị chặn bởi $X$ không? (tight)
2. Điều kiện đề bài: Số cuối cùng có thỏa mãn không? (prop)
3. Tính hợp lệ: Có số 0 đầu không mong muốn không? (started)

Các chữ số cụ thể đã chọn trước pos (ngoài thông tin đã tóm gọn trong tight, prop, started) là không cần thiết. Bộ tứ (pos, tight, prop, started) (hoặc biến thể) là đủ để xác định bài toán con, cho phép dùng memoization (lưu kết quả đã tính) hiệu quả.

Bảng Tóm Tắt Trạng Thái DP:

3. Vũ Điệu Đệ Quy: Bước Chuyển và Điểm Dừng

Cách tiếp cận phổ biến nhất là dùng đệ quy có nhớ (Top-Down DP hay Memoization).

• Hàm Đệ Quy: Viết hàm solve(pos, tight, prop, started) trả về kết quả cho bài toán con tương ứng.
• Memoization - Phép Màu Trí Nhớ: Dùng mảng dp lưu kết quả đã tính. Trước khi tính, kiểm tra xem dp[pos][tight][prop][started] đã có giá trị chưa (khác -1?). Nếu có, trả về luôn. Xong!
  • Ví von vui: Đệ quy không nhớ như anh chàng "não cá vàng", hỏi "2+3=?" thì tính, lát hỏi lại thì... tính lại từ đầu! Memoization là đưa cho ảnh cuốn sổ: tính xong ghi vào, lần sau giở sổ ra đọc, khỏi tính lại! Nhanh hơn hẳn!
• Điểm Dừng (Base Case): Khi "xây" xong số (pos vượt qua vị trí cuối). Tại đây, kiểm tra prop (ví dụ rem == 0). Nếu thỏa mãn, trả về 1 (tìm được 1 số tốt), nếu không trả về 0.
• Bước Chuyển (Transition) - Trái Tim Thuật Toán:
  1. Xác định limit: Nếu tight == true, limit = digit[pos] (chữ số tại pos của $X$). Nếu tight == false, limit = 9.
  2. Lặp d từ 0 đến limit: Duyệt qua các chữ số có thể chọn.
  3. Xử lý started và gọi đệ quy: Với mỗi d:
     • Tính newPos = pos + 1.
     • Tính newTight = tight && (d == limit) (Chỉ true khi đang tight và chọn đúng limit).
     • Tính newProp (cập nhật tổng, dư, hiệu...) chỉ khi started == true hoặc d > 0. Nếu started == false và d == 0, prop thường giữ nguyên.
     • Tính newStarted = started || (d > 0) (Chỉ cần started cũ là true hoặc d mới > 0).
     • Gọi đệ quy: resultD = solve(newPos, newTight, newProp, newStarted).
  4. Tổng hợp kết quả: Cộng dồn resultD vào totalResult (nhớ xử lý modulo nếu cần).
  5. Lưu và trả về: Trước khi return, lưu totalResult vào dp[pos][tight][prop][started].
     • Lưu ý: Thường chỉ lưu khi tight == false. Vì trạng thái tight == true ít lặp lại (chỉ đi theo 1 nhánh bám sát $X$), lưu lại có thể không hiệu quả. Nhưng nếu muốn code đơn giản, cứ lưu hết cũng được, miễn là mảng dp đủ to.

Vai trò của tight trong vòng lặp: Nó như "bảo vệ" của vòng lặp d.

• Nếu tight == false (đã đi lệch khỏi $X$): Bảo vệ cho phép đi thoải mái từ 0 đến 9.
• Nếu tight == true (đang bám sát $X$): Bảo vệ chặn lại, không cho chọn d lớn hơn digits[pos].

Việc bạn chọn d nào khi tight == true sẽ quyết định newTight cho bước sau, tạo logic chặt chẽ.

4. Thực Hành Thôi: Ví Dụ "Kinh Điển"

Bài toán: Đếm số nguyên dương trong khoảng $[L, R]$ ($L, R \le 10^{18}$) có tổng các chữ số chia hết cho $D$.

Phân tích và giải:

1. Công thức: Kết quả $= G(R, D) - G(L-1, D)$, với $G(X, D)$ là số lượng số $n$ ($0 \le n \le X$) có tổng chữ số chia hết cho $D$.
2. Hàm $G(X, D)$:
   • Chuyển $X$ thành vector/chuỗi digits.
   • Khởi tạo dp[maxLen][maxRem][2][2] với -1 (maxLen ~ 19, maxRem = $D$, 2 cho tight, 2 cho started).
   • Gọi hàm đệ quy chính: solve(0, true, 0, false).
3. Hàm solve(pos, tight, rem, started):
   • Input: pos, tight, rem (số dư hiện tại của tổng khi chia $D$), started.
   • Output: Số cách hoàn thành số từ pos.
   • Base Case: pos == digits.size(). Nếu started == true và rem == 0, trả về 1, ngược lại trả về 0.
   • Memoization: Nếu tight == false và dp[pos][rem][started] đã tính, trả về.
   • Transition:
     • ans = 0.
     • limit = (tight) ? digits[pos] : 9.
     • Lặp d từ 0 đến limit:
       • newTight = tight && (d == limit).
       • Nếu started == false và d == 0:
         • ans += solve(pos + 1, newTight, 0, false) (vẫn chưa bắt đầu).
       • Ngược lại (started == true hoặc d > 0):
         • new_rem = (rem + d) % D.
         • ans += solve(pos + 1, newTight, newRem, true) (đã bắt đầu, cập nhật dư).
       • (Nhớ modulo ans nếu cần).
   • Lưu kết quả: Nếu tight == false, dp[pos][rem][started] = ans.
   • Trả về ans.
4. Kết quả cuối: Tính $G(R, D)$ và $G(L-1, D)$ rồi trừ.
   • Cực kỳ lưu ý: Xử lý $G(0)$. Nếu $G(0)$ trả về 1 (tính cả số 0) và đề chỉ yêu cầu số dương, thì kết quả cuối có thể cần điều chỉnh (ví dụ: $(G(R)-1) - (G(L-1)-1)$ hoặc $G(R) - G(L-1)$ tùy cách định nghĩa $G$). Cách an toàn là định nghĩa rõ $G(X)$ đếm số $\ge 0$ hay $> 0$. Nếu $G(X)$ đếm số $\ge 0$, thì $G(R) - G(L-1)$ là số lượng số trong $[L, R]$ thỏa mãn.

Code minh họa (C++):

// dp[pos][rem][tightFlag][startedFlag]
// Kích thước cần đủ lớn: ví dụ [20][100][2][2] nếu D <= 100
long long dp[20][100][2][2];
string s; // Chuỗi biểu diễn số X
int D; // Số chia D // pos: vị trí hiện tại
// rem: số dư của tổng các chữ số đã chọn chia cho D
// tight: cờ ràng buộc (1: bị giới hạn bởi s[pos], 0: không giới hạn, có thể chọn 0-9)
// started: cờ đã bắt đầu tạo số (1: đã có chữ số khác 0, 0: chưa, đang là số 0 ở đầu)
long long solve(int pos, int rem, bool tight, bool started)
{ // Base Case: Đã đi hết các chữ số if (pos == s.length()) { // Nếu số đã bắt đầu và tổng chia hết cho D (dư 0) thì là 1 cách hợp lệ // Nếu started = false tức là chỉ tạo ra số 0 (hoặc chuỗi rỗng), không tính nếu đề yêu cầu số dương > 0 // Tuy nhiên, hàm G(X) thường định nghĩa cho số >= 0, nên ta vẫn tính cả số 0 ở đây return (started && rem == 0); } // Memoization: Chỉ lưu và sử dụng khi không còn ràng buộc (tight = false) // Tham số tight được dùng trong key của dp để phân biệt trạng thái if (dp[pos][rem][tight][started] != -1) { return dp[pos][rem][tight][started]; } long long ans = 0; // Xác định giới hạn trên cho chữ số d int limit = tight ? (s[pos] - '0') : 9; // Lặp qua các chữ số d có thể chọn for (int d = 0; d <= limit; ++d) { // Cập nhật tight cho lần gọi đệ quy tiếp theo // Chỉ giữ tight = true nếu tight hiện tại là true VÀ chọn chữ số d bằng đúng giới hạn bool newTight = tight && (d == limit); // Xử lý trường hợp số 0 đứng đầu if (!started && d == 0) { // Nếu chưa bắt đầu và chọn số 0 -> vẫn chưa bắt đầu, số dư vẫn là 0 ans = (ans + solve(pos + 1, newTight, 0, false)); // Thêm modulo nếu cần: ans %= MOD; } else { // Nếu đã bắt đầu HOẶC chọn chữ số d > 0 -> số đã chính thức bắt đầu // Cập nhật số dư mới int newRem = (rem + d) % D; ans = (ans + solve(pos + 1, newTight, newRem, true)); // Thêm modulo nếu cần: ans %= MOD; } } // Lưu kết quả vào bảng dp (có thể lưu cả khi tight=true nếu muốn, chỉ tốn thêm bộ nhớ) return dp[pos][rem][tight][started] = ans;
} // Hàm tính G(X, D): đếm số n (0 <= n <= X) có tổng chữ số chia hết cho D
long long G(long long X)
{ if (X < 0) return 0; // Trường hợp X = 0: số 0 có tổng chữ số là 0, chia hết cho mọi D // Trả về 1 vì có một số (số 0) thỏa mãn trong khoảng [0, 0] if (X == 0) return 1; s = to_string(X); memset(dp, -1, sizeof(dp)); // Gọi hàm solve ban đầu: vị trí 0, ràng buộc true, số dư 0, chưa bắt đầu // Kết quả của solve này đã bao gồm cả số 0 (nếu nó <= X) // vì base case trả về 1 khi rem=0 và started=true (số 0 không làm started=true) // Tuy nhiên, cách cài đặt trên sẽ tính cả số 0 như một kết quả hợp lệ // nếu started=false, rem=0 ở base case trả về 1. // Nhưng cách hiện tại: `return (started && rem == 0)` đảm bảo số 0 không được đếm // Do đó, G(X) này trả về số lượng số DƯƠNG <= X thỏa mãn. // Để tính cả số 0, cần logic khác hoặc cộng 1 vào cuối nếu D chia hết 0. // Giả định: G(X) đếm số n trong [0, X] thỏa mãn. Số 0 thỏa mãn. memset(dp, -1, sizeof(dp)); // Để tính cả số 0, cần một cách gọi solve hoặc base case khác. // Cách đơn giản: tính số dương rồi cộng 1. long long countPositive = solve(0, 0, true, false); // Số 0 có tổng chữ số là 0, luôn chia hết cho D // Nên G(X) đếm số trong [0,X] sẽ là countPositive + 1 return countPositive + 1; // Tính cả số 0
} int main()
{ long long L, R; cin >> L >> R >> D; // Đọc L, R, và D // Kết quả = G(R) - G(L-1) // G(X) của chúng ta đếm số trong [0, X] thỏa mãn long long countR = G(R); long long countLMinus1 = G(L - 1); long long result = countR - countLMinus1; cout << result; // Thêm modulo nếu cần return 0;
}

Lưu ý quan trọng về code mẫu: Cách xử lý số 0 và định nghĩa chính xác của hàm $G(X)$ (đếm số $\ge 0$ hay $>0$) cần được xem xét kỹ lưỡng tùy theo yêu cầu cụ thể của từng bài toán để đảm bảo công thức $G(R) - G(L-1)$ cho ra kết quả đúng. Code trên giả định $G(X)$ đếm số trong $[0, X]$ và cộng 1 vào cuối để tính cả số 0.

5. Tổng Kết: Tung Hoành Cùng Digit DP!

Ok nhe! Vậy là anh em mình đã "bóc tách" kỹ thuật Digit DP. Hy vọng giờ anh em không còn thấy nó "ghê gớm" nữa.

Điểm lại "bí kíp":

• Nhận diện: Đếm số/tính tổng trong khoảng lớn dựa trên tính chất chữ số $\rightarrow$ Nghĩ ngay Digit DP.
• Công thức vàng: $G(B) - G(A-1)$. Xây hàm $G(X)$ là then chốt.
• Trạng thái "bất hủ": Nhớ bộ tứ (pos, tight, prop, started) (hoặc biến thể). Hiểu rõ vai trò tight và started.
• Cách tiếp cận: Đệ quy có nhớ (Top-Down) thường dễ code hơn.
• Cốt lõi: Nắm vững base case và logic transition.

Lời khuyên "chí mạng" để master Digit DP:

1. Hiểu sâu trạng thái: Đừng code như cái máy. Tự hỏi tại sao cần trạng thái này? tight thay đổi thế nào? started ảnh hưởng ra sao?
2. Code cẩn thận: Debug DP khá "khoai". Viết code rõ ràng, check kỹ base case, limit, cập nhật trạng thái.
3. Luyện tập, luyện tập, luyện tập! Không có đường tắt. Giải nhiều bài trên Codeforces, AtCoder, VNOI... sẽ giúp nhận ra pattern và phản xạ nhanh hơn.

Giờ anh em đã có "vũ khí" Digit DP rồi đấy! Tự tin dùng nó để chinh phục bài toán đếm số "khó nhằn", tối ưu code, và làm đối thủ "khóc thét" (vì code nhanh và chuẩn quá!).

Chúc anh em code vui! Nếu thấy bài viết này bổ ích, hài hước, hay muốn "tám" thêm, cứ comment bên dưới nhé! 😉