Digit DP

Đếm trên [0, X] bằng cờ chặn

Gọi $P(x)$ là tính chất cần kiểm và $F(X)$ là số lượng số nguyên $x$ thỏa $0 \le x \le X$ và $P(x)$. Các số từ 0 tới $b$ gồm các số từ 0 tới $a - 1$ cộng các số từ $a$ tới $b$, nên số lượng $x$ thỏa $P$ trong đoạn $[a, b]$ là

Đây là mẹo của tổng tiền tố ở bài 02: đếm trên hai tiền tố rồi trừ. Khi $a = 0$ ta cần $F(-1)$, đếm trên đoạn rỗng, bằng 0; hàm $F$ phải trả 0 ngay khi $X < 0$, trước khi tách chữ số. Khi $a$ cho dạng chuỗi dài hàng nghìn chữ số, tính $a - 1$ rất phiền; khi đó dùng $F(b) - F(a) + [P(a)]$, trong đó $[P(a)]$ bằng 1 nếu $a$ hợp lệ, kiểm thẳng trên các chữ số của $a$.

Tách theo vị trí rẽ nhánh. Cho $X$ có $n$ chữ số $x_1 x_2 \dots x_n$, với $x_1$ cao nhất. Mọi $y \in [0, X]$ viết được thành đúng $n$ chữ số bằng cách thêm số 0 vào đầu (với $n = 4$, số 42 thành 0042). Hai chuỗi cùng độ dài so sánh theo vị trí đầu tiên chúng khác nhau, trùng với thứ tự giá trị, nên mỗi $y < X$ nằm trong đúng một khối $(i, c)$: $y$ trùng $X$ ở $i - 1$ chữ số đầu, chữ số thứ $i$ bằng $c < x_i$, và $n - i$ chữ số cuối tùy ý. Các khối rời nhau; hợp của chúng cùng với $\{X\}$ là cả $[0, X]$. Với $X = 2718$ ta có $2 \cdot 1000 + 7 \cdot 100 + 1 \cdot 10 + 8 + 1 = 2719$ số.

Điểm mấu chốt: trong một khối, phần đầu đã cố định còn phần cuối hoàn toàn tự do, nên số cách điền phần cuối chỉ phụ thuộc vào còn bao nhiêu chữ số và phần đầu để lại “tình trạng” gì, không phụ thuộc $X$.

Đệ quy có nhớ với cờ chặn. Gọi $\sigma$ là trạng thái của phần đã điền. Hàm go(pos, σ, tight) trả về số cách điền các vị trí pos, ..., n-1 sao cho cả số cuối cùng hợp lệ và không vượt $X$; dig[0] là chữ số cao nhất. Cờ tight bằng đúng khi các chữ số đã điền trùng với dig[0..pos-1]; khi đó chữ số kế tiếp chỉ được tới dig[pos], còn nếu không thì được tới 9. Chọn chữ số $d$ thì cờ mới là tight && d == hi. Các lời gọi có tight bật tạo thành một chuỗi đi theo từng chữ số của $X$; mỗi lần rời chuỗi bằng chữ số $c < x_i$ ta rơi vào đúng khối $(i, c)$, nên không đếm thiếu, không đếm trùng, và chuỗi kết thúc tại chính $X$.

Một lời gọi tự do go(pos, σ, false) chỉ phụ thuộc vào số chữ số còn lại rest = n - pos và $\sigma$, vì mọi chữ số phía sau đều chạy từ 0 đến 9 dù $X$ là bao nhiêu. Ta nhớ nó theo khóa (rest, σ). Lời gọi đang bị chặn thì giá trị phụ thuộc phần còn lại của $X$, nên không ghi; cũng không cần, vì chỉ có $n$ lời gọi như vậy. Gọi $|S|$ là số giá trị mà $\sigma$ có thể nhận; số trạng thái tự do là $n \cdot |S|$, mỗi trạng thái xét 10 chữ số, nên cả bảng tốn $O(10 \cdot n \cdot |S|)$.

Chương trình dưới đếm các số trong $[a, b]$ có tổng chữ số bằng $s$; trạng thái là tổng đã điền, $|S| \le 172$.

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

ll s, memo[20][200];
bool vis[20][200];
vector<ll> dig;

ll go(ll pos, ll sum, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return sum == s;
    if (!tight && vis[rest][sum]) return memo[rest][sum];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) res += go(pos + 1, sum + d, tight && d == hi);
    if (!tight) {
        vis[rest][sum] = 1;
        memo[rest][sum] = res;
    }
    return res;
}

ll F(ll X) {
    if (X < 0) return 0;
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 0, 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b;
    cin >> a >> b >> s;
    cout << F(b) - F(a - 1) << '\n';
}

Input0 2718 3

Output19

Chạy tay theo khối: vị trí 1 với $c = 0$ cần tổng 3 từ ba chữ số tự do, 10 cách; $c = 1$ cần tổng 2, 6 cách. Vị trí 2 (tiền tố 2): $c = 0$ cần tổng 1 từ hai chữ số, 2 cách; $c = 1$ cần tổng 0, 1 cách. Tiền tố 27 đã có tổng 9, vượt 3. Tổng $10 + 6 + 2 + 1 = 19$. Khóa của bảng là rest chứ không phải pos: $F(b)$ và $F(a - 1)$ có thể có số chữ số khác nhau, và chỉ rest mới mang cùng ý nghĩa ở cả hai lần gọi. Nhờ vậy một bảng dùng chung cho mọi lần gọi $F$; chỉ khi tham số của bài (ở đây là $s$) đổi giữa các truy vấn mới phải xóa bảng.

Ví dụDấu Vết 4 Và 9

Đề. Cho $1 \le A \le B \le 10^{18}$. Đếm các số trong $[A, B]$ có ít nhất một chữ số bằng 4 hoặc 9.

Lời giải. Trạng thái là một cờ has: phần đã điền đã có chữ số 4 hoặc 9 chưa. Đặt chữ số $d$ thì has mới là has || d == 4 || d == 9; ở cuối trả has. Số 0 đệm không phải 4 hay 9 nên không làm hỏng cờ. Chỉ có $19 \cdot 2$ trạng thái tự do. Cách khác là đếm bù: số không chứa 4 và 9 trong $[0, X]$ chỉ cần cờ chặn, rồi lấy $X + 1$ trừ đi. Với ví dụ, cả bảy số từ 39 tới 45 đều có 4 hoặc 9.

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

ll memo[20][2];
bool vis[20][2];
vector<ll> dig;

ll go(ll pos, bool has, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return has;
    if (!tight && vis[rest][has]) return memo[rest][has];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) res += go(pos + 1, has || d == 4 || d == 9, tight && d == hi);
    if (!tight) {
        vis[rest][has] = 1;
        memo[rest][has] = res;
    }
    return res;
}

ll F(ll X) {
    if (X < 0) return 0;
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 0, 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b;
    cin >> a >> b;
    cout << F(b) - F(a - 1) << '\n';
}

Input39 45

Output7

Số 0 dẫn đầu và cờ bắt đầu

Đệm số 0 cho đủ $n$ chữ số rất tiện, nhưng chương trình giờ thấy số 42 là 0042 và đọc hai số 0 đệm như hai chữ số thật. Với tổng chữ số, phần dư hay bội chung nhỏ nhất của các chữ số khác 0, số 0 đứng đầu vô hại vì không làm đổi tổng, phần dư hay bội chung. Nhưng với “không có chữ số 0”, “không có hai chữ số kề nhau bằng nhau”, “tích các chữ số” hay “mỗi chữ số xuất hiện chẵn lần”, các số 0 đệm phải bị bỏ qua.

Cách xử lý là thêm cờ bắt đầu (st): đã đặt chữ số khác 0 chưa. Chưa bắt đầu mà chọn 0 thì vẫn chưa bắt đầu và trạng thái của tính chất không đổi; chọn chữ số khác 0 thì bắt đầu. Từ lúc bắt đầu, mọi chữ số, kể cả 0, là chữ số thật.

Chương trình dưới đếm số $x$ trong $[1, N]$ không có chữ số 0. Chưa bắt đầu mà chọn 0 là số 0 đệm, cho qua; đã bắt đầu mà chọn 0 là chữ số 0 thật, bị cấm. Ở cuối, đường đi chưa bắt đầu suốt $n$ vị trí chính là số 0, nên return st loại luôn số 0 khỏi $[1, N]$.

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

ll n, memo[20][2];
bool vis[20][2];
vector<ll> dig;

ll go(ll pos, bool st, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return st;
    if (!tight && vis[rest][st]) return memo[rest][st];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) {
        if (d == 0 && st) continue;
        res += go(pos + 1, st || d > 0, tight && d == hi);
    }
    if (!tight) {
        vis[rest][st] = 1;
        memo[rest][st] = res;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (char c : to_string(n)) dig.push_back(c - '0');
    cout << go(0, 0, 1) << '\n';
}

Input120

Output99

Kiểm tay: có 9 số một chữ số, $9 \cdot 9 = 81$ số hai chữ số không có số 0, và với ba chữ số chỉ 111 đến 119 thỏa, tổng $9 + 81 + 9 = 99$.

Cờ bắt đầu không nhất thiết là một chiều riêng của trạng thái. Khi trạng thái đã có “chữ số vừa điền”, ta thêm cho nó giá trị 10 nghĩa là “chưa có chữ số nào”, như ở ví dụ dưới.

Ví dụHai Chữ Số Kề Nhau

Đề. Đếm các số trong $[a, b]$, $0 \le a \le b \le 10^{18}$, không có hai chữ số liền nhau bằng nhau trong biểu diễn thập phân. Số 0 hợp lệ.

Lời giải. Tính chất chỉ phụ thuộc chữ số đứng ngay trước, nhưng số 0 đệm phải bị bỏ qua: 42 hợp lệ, còn 0042 đọc như thể có hai số 0 liền nhau. Trạng thái là chữ số $p$ vừa đặt, từ 0 đến 9, thêm giá trị 10 nghĩa là “chưa có chữ số nào”. Chọn $d$ bằng $p$ thì bỏ qua; vì $p = 10$ không trùng chữ số nào nên chữ số đầu tiên không bị cấm. Nếu $p = 10$ và $d = 0$ thì $p$ giữ nguyên 10 (số 0 đệm), còn lại $p$ mới bằng $d$. Ở cuối mọi đường còn lại đều hợp lệ, kể cả đường toàn 0 biểu diễn số 0. Hai số 0 liền nhau ở giữa số, như trong 100, vẫn bị bắt vì lúc đó $p = 0$ là chữ số thật.

Có $19 \cdot 11$ trạng thái tự do. Kiểm tay: $F(99) = 10 + 81 = 91$; trong 98, 99 chỉ 99 bị loại nên $F(97) = 90$; trong 100, 101, 102 chỉ 100 bị loại nên $F(102) = 93$. Đoạn $[98, 102]$ có $93 - 90 = 3$ số.

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

ll memo[20][11];
bool vis[20][11];
vector<ll> dig;

ll go(ll pos, ll p, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return 1;
    if (!tight && vis[rest][p]) return memo[rest][p];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) {
        if (d == p) continue;
        res += go(pos + 1, (p == 10 && d == 0) ? 10 : d, tight && d == hi);
    }
    if (!tight) {
        vis[rest][p] = 1;
        memo[rest][p] = res;
    }
    return res;
}

ll F(ll X) {
    if (X < 0) return 0;
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 10, 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b;
    cin >> a >> b;
    cout << F(b) - F(a - 1) << '\n';
}

Input98 102

Output3

Chọn trạng thái

Trạng thái trả lời câu hỏi: chỉ biết những điều này về phần đã điền, ta có đủ để đếm phần còn lại không? Hai phần đầu có cùng thông tin thì có cùng tương lai nên được gộp, và đó là chỗ quy hoạch động tiết kiệm. Ngược lại, thiếu thông tin thì hai phần đầu có tương lai khác nhau bị gộp nhầm, và đáp án sai.

Hàng cuối: tích các chữ số chỉ có dạng $2^a 3^b 5^c 7^d$, và với $K \le 10^9$ chỉ có 5194 giá trị không vượt $K$. Mọi tích lớn hơn $K$ được gộp thành một trạng thái “quá $K$”, nhưng không được cắt nhánh đó: một chữ số 0 thật về sau đưa tích về 0, và $0 \le K$. Khi $n$ lớn thì trạng thái càng phải gọn: tổng chữ số chia hết cho $D$ chỉ cần nhớ phần dư theo $D$, vì hai tổng cùng phần dư có cùng tương lai.

Thời gian là $n \cdot |S| \cdot 10$, nên với $n = 19$ thì $|S|$ cỡ $10^5$ vẫn nhẹ (khoảng $2 \cdot 10^7$ phép tính), còn $|S| \approx 10^6$ đã chạm giới hạn cả thời gian lẫn bộ nhớ. Mặt nạ tập chữ số sẽ gặp lại ở bài 15, và trạng thái “đang khớp tới đâu trong các mẫu cho trước” cần Aho-Corasick ở bài 73.

Ví dụTổng Chữ Số Chia Hết

Đề. Cho số nguyên dương $K < 10^{10000}$ dạng chuỗi và $D \le 100$. Đếm các số $1 \le x \le K$ có tổng chữ số chia hết cho $D$, theo modulo $10^9 + 7$.

Lời giải. Tổng chữ số tới $9 \cdot 10^4$, nhưng chỉ phần dư của nó theo $D$ ảnh hưởng tới tương lai, nên trạng thái là phần dư $r$; đặt chữ số $d$ thì $r \to (r + d) \bmod D$. Cận là chuỗi, nên dig lấy thẳng từ chuỗi, và đáp án đếm theo modulo. Số 0 đệm không đổi tổng nên không cần cờ bắt đầu, nhưng hàm đếm trên $[0, K]$ có tính số 0 (tổng 0 chia hết cho mọi $D$), nên trừ 1. Có $10^4 \cdot 100$ trạng thái tự do, mỗi trạng thái 10 chữ số: $10^7$ phép. Độ sâu đệ quy bằng số chữ số, $10^4$ tầng, vẫn an toàn.

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

const ll MOD = 1e9 + 7;
string K;
ll D, n, memo[10005][105];

ll go(ll pos, ll r, bool tight) {
    ll rest = n - pos;
    if (rest == 0) return r == 0;
    if (!tight && memo[rest][r] != -1) return memo[rest][r];
    ll hi = tight ? K[pos] - '0' : 9, res = 0;
    for (ll d = 0; d <= hi; d++) res = (res + go(pos + 1, (r + d) % D, tight && d == hi)) % MOD;
    if (!tight) memo[rest][r] = res;
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> K >> D;
    n = K.size();
    memset(memo, -1, sizeof(memo));
    cout << (go(0, 0, 1) - 1 + MOD) % MOD << '\n';
}

Input20
2

Output10

Ví dụChia Hết Cho Mọi Chữ Số

Đề. Có $T \le 10$ truy vấn, mỗi truy vấn cho $1 \le l \le r \le 9 \cdot 10^{18}$; đếm các số trong $[l, r]$ chia hết cho từng chữ số khác 0 của nó.

Lời giải. Điều kiện nhắc tới toàn bộ số $x$: $x$ phải chia hết cho bội chung nhỏ nhất $L$ của các chữ số khác 0. Ta chưa biết $L$ khi mới điền một phần, nhưng $L$ luôn là ước của $\mathrm{lcm}(1, \dots, 9) = 2520$, và 2520 chỉ có 48 ước. Vì $L \mid 2520$ nên $L \mid x$ khi và chỉ khi $L \mid (x \bmod 2520)$. Vậy trạng thái gồm phần dư $r$ của phần đã điền theo 2520 và ước $L$ hiện tại. Số 0 đệm không đổi $r$ cũng không đổi $L$, nên không cần cờ bắt đầu; số 0 được đếm ở cả $F(r)$ lẫn $F(l - 1)$ rồi triệt tiêu.

Bước 1: đánh số các ước của 2520 và bảng chuyển. dv liệt kê 48 ước, id[v] cho số thứ tự của ước $v$. nxt[i][d] là số thứ tự của $\mathrm{lcm}(\text{dv}_i, d)$ khi đặt thêm chữ số $d \ne 0$; chữ số 0 giữ nguyên $L$. Bảng dựng một lần, chuyển trạng thái chỉ còn là một lần tra.

for (ll v = 1; v <= M; v++)
    if (M % v == 0) {
        id[v] = dv.size();
        dv.push_back(v);
    }
for (ll i = 0; i < (ll)dv.size(); i++)
    for (ll d = 0; d <= 9; d++) nxt[i][d] = id[d == 0 ? dv[i] : lcm(dv[i], d)];

Bước 2: đếm theo khung chữ số. Đặt $d$ thì $r \to (10r + d) \bmod 2520$ và $L \to$ nxt[li][d]. Ở cuối, số hợp lệ khi $L \mid r$. Trạng thái tự do (rest, r, li) được nhớ trong memo, đánh dấu chưa tính bằng $-1$.

ll go(ll pos, ll r, ll li, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return r % dv[li] == 0;
    if (!tight && memo[rest][r][li] != -1) return memo[rest][r][li];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) res += go(pos + 1, (r * 10 + d) % M, nxt[li][d], tight && d == hi);
    if (!tight) memo[rest][r][li] = res;
    return res;
}

Bảng memo không phụ thuộc truy vấn (chỉ phụ thuộc số chữ số còn lại, không phụ thuộc cận), nên dùng chung cho cả $T$ truy vấn. Với ví dụ, trong $[10, 20]$ các số 10, 11, 12, 15, 20 hợp lệ.

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

const ll M = 2520;
ll t, id[M + 1], nxt[48][10], memo[20][M][48];
vector<ll> dv, dig;

ll go(ll pos, ll r, ll li, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return r % dv[li] == 0;
    if (!tight && memo[rest][r][li] != -1) return memo[rest][r][li];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) res += go(pos + 1, (r * 10 + d) % M, nxt[li][d], tight && d == hi);
    if (!tight) memo[rest][r][li] = res;
    return res;
}

ll F(ll X) {
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 0, id[1], 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (ll v = 1; v <= M; v++)
        if (M % v == 0) {
            id[v] = dv.size();
            dv.push_back(v);
        }
    for (ll i = 0; i < (ll)dv.size(); i++)
        for (ll d = 0; d <= 9; d++) nxt[i][d] = id[d == 0 ? dv[i] : lcm(dv[i], d)];
    memset(memo, -1, sizeof(memo));
    cin >> t;
    while (t--) {
        ll l, r;
        cin >> l >> r;
        cout << F(r) - F(l - 1) << '\n';
    }
}

Input1
10 20

Output5

Có $19 \cdot 2520 \cdot 48 \approx 2{,}3 \cdot 10^6$ trạng thái tự do, mỗi trạng thái thử 10 chữ số: $2{,}3 \cdot 10^7$ phép và khoảng 19 MB bảng.

Đếm kèm tổng

Nhiều bài hỏi tổng của một đại lượng trên các số hợp lệ: tổng giá trị, tổng chữ số, tổng số lần xuất hiện một chữ số. Khi đó go trả về một cặp $(C, T)$ thay vì một số.

Với trạng thái còn $r$ chữ số phải điền: $C$ là số cách điền hợp lệ, còn $T$ là tổng, trên mọi cách đó, của giá trị phần đuôi do $r$ chữ số vừa điền tạo thành. Chọn chữ số $d$ cho vị trí kế tiếp, có trọng số $10^{r-1}$; trạng thái con trả về $(C_d, T_d)$. Mỗi cách của trạng thái con được ghép thêm $d$ ở phía trước, nên giá trị đuôi của nó tăng thêm $d \cdot 10^{r-1}$:

Ở trạng thái xuất phát, phần đuôi chính là cả số, nên $T$ là tổng các số hợp lệ. Nếu đề hỏi theo modulo, lấy modulo sau mỗi phép nhân và để $10^{r-1}$ ở dạng đã lấy modulo. Cần tổng bình phương thì thêm thành phần thứ ba $Q$, vì $(a + v)^2 = a^2 + 2av + v^2$. Cần tổng các chữ số thay vì tổng các số thì trọng số chỉ là $d$, không nhân $10^{r-1}$.

Chương trình sau tính tổng các số trong $[a, b]$ không chứa chữ số 7, với $b \le 10^9$. Tính chất này không cần trạng thái nào ngoài cờ chặn, nên bảng nhớ chỉ có chỉ số rest; mỗi ô là một pair (số cách, tổng).

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

ll pw[20];
bool vis[20];
pair<ll, ll> memo[20];
vector<ll> dig;

pair<ll, ll> go(ll pos, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return {1, 0};
    if (!tight && vis[rest]) return memo[rest];
    ll hi = tight ? dig[pos] : 9;
    pair<ll, ll> res = {0, 0};
    for (ll d = 0; d <= hi; d++) {
        if (d == 7) continue;
        pair<ll, ll> sub = go(pos + 1, tight && d == hi);
        res.first += sub.first;
        res.second += sub.second + d * pw[rest - 1] * sub.first;
    }
    if (!tight) {
        vis[rest] = 1;
        memo[rest] = res;
    }
    return res;
}

ll F(ll X) {
    if (X < 0) return 0;
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 1).second;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    pw[0] = 1;
    for (ll i = 1; i < 19; i++) pw[i] = pw[i - 1] * 10;
    ll a, b;
    cin >> a >> b;
    cout << F(b) - F(a - 1) << '\n';
}

Input1 30

Output414

Kiểm tay: $1 + 2 + \dots + 30 = 465$, bỏ ba số có chữ số 7 là 7, 17, 27 (tổng 51) còn 414. Số 0 đứng đầu không đóng góp gì vào giá trị, nên bài này không cần cờ bắt đầu.

Ví dụTổng Chữ Số Trên Đoạn

Đề. Với mỗi truy vấn $0 \le a \le b \le 10^9$, in $S(a) + S(a + 1) + \dots + S(b)$, với $S(x)$ là tổng chữ số của $x$. Dữ liệu kết thúc bằng cặp -1 -1.

Lời giải. Cùng khuôn cặp $(C, T)$, nhưng $T$ là tổng các chữ số của phần đuôi chứ không phải giá trị, nên chữ số $d$ đóng góp $d \cdot C_d$, không nhân trọng số hàng. Không có ràng buộc nào ngoài cận, nên trạng thái tự do chỉ là rest và bảng dùng chung cho mọi truy vấn. Đáp án là $F(b) - F(a - 1)$ với $F(-1) = 0$; $S(0) = 0$ nên số 0 không ảnh hưởng. Tổng lớn nhất cỡ $81 \cdot 10^9 / 2$, vừa ll. Với ví dụ, $S(1) + \dots + S(9) = 45$ và $S(10) = 1$, tổng 46.

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

bool vis[20];
pair<ll, ll> memo[20];
vector<ll> dig;

pair<ll, ll> go(ll pos, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return {1, 0};
    if (!tight && vis[rest]) return memo[rest];
    ll hi = tight ? dig[pos] : 9;
    pair<ll, ll> res = {0, 0};
    for (ll d = 0; d <= hi; d++) {
        pair<ll, ll> sub = go(pos + 1, tight && d == hi);
        res.first += sub.first;
        res.second += sub.second + d * sub.first;
    }
    if (!tight) {
        vis[rest] = 1;
        memo[rest] = res;
    }
    return res;
}

ll F(ll X) {
    if (X < 0) return 0;
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 1).second;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a, b;
    while (cin >> a >> b && a != -1) cout << F(b) - F(a - 1) << '\n';
}

Input1 10
20 22
-1 -1

Output46
9

Các biến thể hay gặp

Cơ số khác. Trong hệ nhị phân chữ số chỉ là 0 hoặc 1, hi là 1 thay cho 9, và $X$ có tối đa 31 hay 63 bit. Mọi thứ khác giữ nguyên; đếm số $x \le N$ không có hai bit 1 kề nhau chỉ cần nhớ bit vừa điền.

Cận dạng chuỗi. Khi $N$ có tới $10^4$ chữ số, $F$ nhận chuỗi, đáp án lấy theo modulo, và dùng $F(b) - F(a) + [P(a)]$ thay cho $a - 1$. Độ sâu đệ quy bằng $n$, vẫn chấp nhận được; chi phí $n \cdot |S| \cdot 10$ bắt buộc $|S|$ nhỏ.

Số thứ $k$. $F(X)$ không giảm khi $X$ tăng, nên số hợp lệ thứ $k$ là số $X$ nhỏ nhất có $F(X) \ge k$, tìm bằng chặt nhị phân (bài 05). Nhờ bảng nhớ dùng chung, mỗi lần gọi $F$ chỉ tốn $O(10n)$ lời gọi bị chặn.

Điều kiện phụ thuộc cả con số. Khi điều kiện nhắc tới một đại lượng của toàn số, như “$x$ chia hết cho tổng chữ số của $x$”, ta không biết phải chia cho gì khi mới điền một phần. Nhưng tổng chữ số chỉ nhận tối đa $9n$ giá trị. Duyệt từng giá trị $s$ của nó, chạy quy hoạch động chữ số với $s$ cố định (trạng thái gồm tổng và phần dư theo $s$) rồi cộng đáp án qua mọi $s$.

Nhiều cận cùng lúc. Đếm cặp $(a, b)$ với cả hai không vượt $X$ cần hai cờ chặn, mỗi lần chuyển thử mọi cặp chữ số của hai số; trên đoạn $[l, r]$ thì dùng bao hàm loại trừ bốn tiền tố như ở tổng tiền tố hai chiều.

Ví dụSố Thứ K Chứa 666

Đề. Liệt kê tăng dần các số nguyên dương có chứa chuỗi con 666. Với mỗi trong $T \le 100$ truy vấn $k \le 10^7$, in số thứ $k$.

Lời giải. Hai phần: đếm $F(X)$, số các số trong $[0, X]$ chứa 666, rồi tìm số thứ $k$ bằng chặt nhị phân trên $F$.

Bước 1: đếm bằng trạng thái “số chữ số 6 cuối”. $c$ là số chữ số 6 liên tiếp ở cuối phần đã điền, chặn ở 3 nghĩa là “đã gặp 666”. Đặt 6 thì $c$ tăng 1, đặt chữ số khác thì $c$ về 0, còn $c = 3$ thì giữ nguyên dù đặt gì. Ở cuối trả c == 3. Số 0 đệm không phải 6 nên không làm sai $c$.

for (ll d = 0; d <= hi; d++) {
    ll nc = c == 3 ? 3 : (d == 6 ? c + 1 : 0);
    res += go(pos + 1, nc, tight && d == hi);
}

Bước 2: chặt nhị phân trên đáp án. $F$ tăng đúng 1 tại mỗi số chứa 666 và không đổi ở các số khác, nên số thứ $k$ là $X$ nhỏ nhất có $F(X) \ge k$. Đáp án với $k = 10^7$ chưa tới $10^{10}$, nên cận trên $10^{15}$ là dư.

ll l = 1, r = 1e15, res = r;
while (l <= r) {
    ll mid = (l + r) >> 1;
    if (F(mid) >= k) r = (res = mid) - 1;
    else l = mid + 1;
}

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

ll t, memo[20][4];
bool vis[20][4];
vector<ll> dig;

ll go(ll pos, ll c, bool tight) {
    ll rest = dig.size() - pos;
    if (rest == 0) return c == 3;
    if (!tight && vis[rest][c]) return memo[rest][c];
    ll hi = tight ? dig[pos] : 9, res = 0;
    for (ll d = 0; d <= hi; d++) {
        ll nc = c == 3 ? 3 : (d == 6 ? c + 1 : 0);
        res += go(pos + 1, nc, tight && d == hi);
    }
    if (!tight) {
        vis[rest][c] = 1;
        memo[rest][c] = res;
    }
    return res;
}

ll F(ll X) {
    dig.clear();
    for (char c : to_string(X)) dig.push_back(c - '0');
    return go(0, 0, 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        ll k;
        cin >> k;
        ll l = 1, r = 1e15, res = r;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (F(mid) >= k) r = (res = mid) - 1;
            else l = mid + 1;
        }
        cout << res << '\n';
    }
}

Input3
1
2
3

Output666
1666
2666

Mỗi truy vấn khoảng 50 lần gọi $F$; bảng nhớ chỉ có $20 \cdot 4$ trạng thái tự do và dùng chung cho mọi lần gọi, nên mỗi lần gọi chỉ tốn cỡ $19 \cdot 10$ bước trên đường bám cận.