Kẻ Về Nhì (SECOND) (Thi thử HSG9 SQRTOJ 2025 – Ngày 2 Bài 5)
Đề bài
Câu 5. KẺ VỀ NHÌ (4 điểm)
| Mã nguồn | Dữ liệu vào | Dữ liệu ra | Thời gian | Bộ nhớ |
|---|---|---|---|---|
SECOND.* | SECOND.inp | SECOND.out | 1 giây | 1024 MB |
Cho hai số nguyên dương $l, r$. Gọi $f(x)$ là chữ số lớn thứ nhì của $x$. Hãy tính $f(l) + f(l + 1) + \cdots + f(r)$. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi chia lấy dư cho $7 \times 10^9 + 1$.
Dữ liệu vào: Nhập từ file SECOND.inp:
- Dòng đầu tiên gồm một số nguyên dương $t$ là số trường hợp thử nghiệm $(1 \le t \le 15 \times 10^4)$.
- $t$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $l, r$ $(10 \le l \le r \lt 10^{18})$.
Dữ liệu ra: Ghi ra file SECOND.out:
- Gồm $t$ dòng, dòng thứ $i$ gồm duy nhất một số là kết quả của trường hợp thử nghiệm thứ $i$ sau khi chia lấy dư cho $7 \times 10^9 + 1$.
Ràng buộc bổ sung:
- $30\%$ số điểm có $10 \le l \le r \le 10^6$.
- $40\%$ số điểm khác có $t \le 69$, $r - l \le 10^6$.
- $30\%$ số điểm còn lại không có giới hạn gì thêm.
Lưu ý: đề thi gốc đọc/ghi file SECOND.inp / SECOND.out; nộp trên web (SQRTOJ) thì đọc từ bàn phím và in ra màn hình. Code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng.
2
12 24
1023 103015
15Giải thích (theo đề): Với trường hợp thử nghiệm thứ nhất:
- Các số từ $12$ đến $19$ có chữ số lớn thứ nhì là $1$.
- Số $20$ có chữ số lớn thứ nhì là $0$.
- Số $21$ có chữ số lớn thứ nhì là $1$.
- Các số từ $22$ đến $24$ có chữ số lớn thứ nhì là $2$.
- Vậy đáp án cho trường hợp thử nghiệm thứ nhất là $1 \times 8 + 0 + 1 + 2 \times 3 = 15$.
Ghi chú nhỏ: phần giải thích trong đề gốc viết nhầm là "chữ số nhỏ thứ nhì", nhưng các con số trong ví dụ (số $12$ cho ra $1$, số $20$ cho ra $0$…) đều khớp với chữ số lớn thứ nhì như phần đề bài, nên mình sửa lại cho thống nhất.
Lời mở đầu
Đây là bài cuối (bài 5) của ngày thi thứ hai trong kỳ thi thử HSG9 của câu lạc bộ SQRT năm 2025. Đề rất ngắn, đọc là hiểu, nhưng để ăn trọn điểm thì cần tới quy hoạch động chữ số khá "nặng đô". Mình sẽ đi theo đúng 3 subtask của đề để các bạn thấy tư duy đi lên từng bước nha. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích kỹ thêm ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. "Chữ số lớn thứ nhì" của $x$ nghĩa là: viết các chữ số của $x$ ra, sắp xếp giảm dần rồi lấy chữ số đứng ở vị trí thứ hai. Chú ý các chữ số trùng nhau vẫn được tính riêng:
- $x = 12$: chữ số giảm dần là $2, 1$ → $f(12) = 1$.
- $x = 22$: chữ số giảm dần là $2, 2$ → $f(22) = 2$ (không phải "không có").
- $x = 1023$: chữ số giảm dần là $3, 2, 1, 0$ → $f(1023) = 2$. Tương tự $1024, \ldots, 1029$ đều có $f = 2$.
- $x = 1030$: chữ số giảm dần là $3, 1, 0, 0$ → $f(1030) = 1$. Vậy test thứ hai là $2 \times 7 + 1 = 15$.
Vì $l \ge 10$ nên số nào cũng có ít nhất 2 chữ số, $f(x)$ luôn xác định.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Tính trước + mảng cộng dồn – O(10^6 · 7 + t)
Ở subtask này $r \le 10^6$ nhưng $t$ vẫn lên tới $15 \times 10^4$, nên với mỗi truy vấn mà duyệt lại từ $l$ tới $r$ thì sẽ chậm ($10^6 \times 1.5 \cdot 10^5$ phép tính). Ta tính trước một lần cho tất cả các số.
Còn tính $f(i)$ thế nào? Ta tách từng chữ số của $i$ (lấy g % 10 rồi g /= 10), đồng thời giữ 2 biến: mx là chữ số lớn nhất và mx_ là chữ số lớn nhì đã gặp. Với mỗi chữ số dig mới:
- Nếu
dig >= mx:digthành lớn nhất mới, lớn nhất cũ bị đẩy xuống làm lớn nhì:mx_ = mx; mx = dig;. Dấu>=(chứ không phải>) giúp xử lý đúng chữ số trùng: số $22$ sẽ chomx = 2, mx_ = 2. - Ngược lại nếu
dig >= mx_:digchỉ thay chỗ lớn nhì:mx_ = dig. - Còn lại thì không đổi gì.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int t;
long long l, r;
int sum[10000005];
signed main(){
if(fopen("SECOND.inp", "r")){
freopen("SECOND.inp", "r", stdin);
freopen("SECOND.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for (int i = 10; i <= 1000000; i ++){
sum[i] = sum[i - 1];
int mx = -1, mx_ = -1;
long long g = i;
while (g){
int dig = g % 10;
if (dig >= mx){
mx_ = mx;
mx = dig;
}
else if (dig >= mx_){
mx_ = dig;
}
g /= 10;
}
sum[i] += mx_;
}
while(t --){
cin >> l >> r;
cout << sum[r] - sum[l - 1] << '\n';
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
N = 1000000
s = [0] * (N + 1)
for i in range(10, N + 1):
mx = mx_ = -1
g = i
while g:
dig = g % 10
if dig >= mx:
mx_ = mx
mx = dig
elif dig >= mx_:
mx_ = dig
g //= 10
s[i] = s[i - 1] + mx_
out = []
for q in range(t):
l = int(data[1 + 2 * q]); r = int(data[2 + 2 * q])
out.append(s[r] - s[l - 1])
print('\n'.join(map(str, out)))
main()Các bạn bấm Tiếp để chạy tay. Vòng for tính trước chạy tới tận $10^6$ nên mình chạy tay chi tiết các số từ $10$ đến $21$ (đủ để thấy cách tách chữ số và cập nhật mx, mx_), sau đó "tua nhanh" phần còn lại trong 1 bước rồi mới tới phần trả lời truy vấn:
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $sum$ có $10^6$ phần tử (trong code khai báo dư $10^7$ cũng không sao vì bộ nhớ cho tới 1024 MB).
- Thời gian: tính trước $10^6$ số, mỗi số tách tối đa 7 chữ số; mỗi truy vấn $O(1)$. Tổng cỡ $7 \cdot 10^6 + t$ phép tính.
Subtask 2Duyệt từng số, suy ra nhanh từ số trước – O(t · (r − l))
Ở subtask này $l, r$ có thể rất lớn (tới $10^{18}$) nhưng đoạn $[l, r]$ ngắn: $r - l \le 10^6$ và chỉ có $t \le 69$ truy vấn. Vậy ta chạy từ $l$ đến $r$ và tìm ra chữ số lớn thứ nhì của từng số để cộng vào. Nếu số nào cũng tách lại hết 18 chữ số thì tốn $69 \times 10^6 \times 18 \approx 1.2 \cdot 10^9$ phép tính – hơi căng với 1 giây. Ta cần tối ưu bước tính $f(i)$.
mx, mx_ của số đằng trước. Còn nếu $i \bmod 10 = 0$ (có nhớ sang hàng chục, nhiều chữ số đổi cùng lúc) – hoặc $i = l$ là số đầu tiên – thì ta xử lý duyệt qua hết các chữ số lại.Cụ thể, khi $i \bmod 10 = d \ne 0$, ta đang có mx, mx_ của $i - 1$. Cần "bỏ" chữ số $d - 1$ và "thêm" chữ số $d$:
- Nếu
mx == d - 1vàmx_ != d - 1: chữ số $d - 1$ là lớn nhất và chỉ xuất hiện đúng 1 lần, tức nó chính là chữ số hàng đơn vị. Thay nó bằng $d$ thì lớn nhất thành $d$, còn lớn nhì không đổi:mx = d. - Ngược lại, chữ số $d - 1$ hoặc nhỏ hơn
mx, hoặc là lớn nhất nhưng xuất hiện từ 2 lần trở lên. Khi đó ta chỉ cần coi như thêm chữ số $d$ vào (giống hệt cách cập nhật ở subtask 1) mà không cần "bỏ" $d - 1$ đi. Lý do: $d - 1$ nhỏ hơn $d$ và nếu nó đang đứng ở vị trí lớn nhì thì $d$ (lớn hơn nó) sẽ thế chỗ nó; còn nếu nó không nằm trong top 2 thì bỏ nó đi cũng chẳng ảnh hưởng gì.
Ví dụ: $i - 1 = 1234$ có mx = 4, mx_ = 3. Sang $i = 1235$: mx = 4 = d - 1 và mx_ = 3 != 4 → trường hợp 1, mx = 5, lớn nhì vẫn là $3$ ✔. Hay $i - 1 = 2888$ (mx = mx_ = 8) sang $i = 2889$: trường hợp 2, thêm chữ số $9$ → mx = 9, mx_ = 8 ✔.
Các bạn nhập một đoạn $[l, r]$ ngắn vào khung minh hoạ dưới đây và bấm Tiếp để xem từng số được cập nhật theo luật nào (viền đỏ = chữ số lớn nhất, viền xanh = chữ số lớn nhì):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int t;
long long l, r;
signed main(){
if(fopen("SECOND.inp", "r")){
freopen("SECOND.inp", "r", stdin);
freopen("SECOND.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
if (t <= 69){
while (t --){
cin >> l >> r;
int sum = 0;
int mx = -1, mx_ = -1;
for (long long i = l; i <= r; i ++){
if (i % 10 == 0 || i == l){
mx = -1, mx_ = -1;
long long g = i;
while (g){
int dig = g % 10;
if (dig >= mx){
mx_ = mx;
mx = dig;
}
else if (dig >= mx_){
mx_ = dig;
}
g /= 10;
}
sum += mx_;
}
else{
if (mx == i % 10 - 1 && mx_ != i % 10 - 1){
mx = i % 10;
}
else if (i % 10 >= mx){
mx_ = mx;
mx = i % 10;
}
else if (i % 10 >= mx_){
mx_ = i % 10;
}
sum += mx_;
}
}
cout << sum << '\n';
}
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
if t > 69:
return
out = []
for q in range(t):
l = int(data[1 + 2 * q]); r = int(data[2 + 2 * q])
total = 0
mx = mx_ = -1
for i in range(l, r + 1):
d = i % 10
if d == 0 or i == l:
mx = mx_ = -1
g = i
while g:
dig = g % 10
if dig >= mx:
mx_ = mx
mx = dig
elif dig >= mx_:
mx_ = dig
g //= 10
else:
if mx == d - 1 and mx_ != d - 1:
mx = d
elif d >= mx:
mx_ = mx
mx = d
elif d >= mx_:
mx_ = d
total += mx_
out.append(total)
print('\n'.join(map(str, out)))
main()Code chỉ xử lý khi t <= 69 (đúng giới hạn subtask này). Biến sum để kiểu int vẫn an toàn vì tối đa $(10^6 + 1) \times 9 \approx 9 \cdot 10^6$, chưa cần chia lấy dư. Các bạn chạy tay để thấy rõ khi nào code tách lại toàn bộ chữ số, khi nào chỉ cập nhật nhanh:
Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ vài biến: $O(1)$.
- Thời gian: mỗi truy vấn duyệt $r - l + 1$ số; cứ 10 số mới có 1 số phải tách lại đủ 18 chữ số, 9 số còn lại cập nhật $O(1)$. Nên độ phức tạp mỗi truy vấn là $O(r - l)$ (cỡ $(r - l) \cdot (1 + 18/10)$ phép tính), tổng $O(t \cdot (r - l))$.
Subtask 3Quy hoạch động chữ số – O(19 · 10 + t · 19)
Ta gọi $F(x)$ là tổng các chữ số lớn thứ nhì từ $10$ đến $x$ (trong code là hàm que(x); quy ước $F(x) = 0$ khi $x \lt 10$). Dễ thấy để tính tổng các chữ số lớn thứ nhì từ đoạn $l$ đến $r$ sẽ bằng $F(r) - F(l - 1)$ – y hệt ý tưởng mảng cộng dồn ở subtask 1, chỉ là bây giờ $F$ phải được tính bằng công thức chứ không lưu sẵn được.
Chia các số thành từng nhóm
Chúng ta sẽ xem xét cách tính $F(x)$. Gọi $s$ là xâu các chữ số của $x$ và $n$ là số chữ số của $x$ (đánh số vị trí $0, 1, \ldots, n - 1$ từ trái sang). Xét một số $y \lt x$, gọi $n_y$ là số chữ số của $y$. Ta sẽ thêm $n - n_y$ số $0$ vào đằng trước $y$ để cho $y$ cũng có đúng $n$ chữ số. Khi này, nhận xét: nếu $y \lt x$ thì ở vị trí nhỏ nhất $i$ mà chữ số thứ $i$ của $y$ và chữ số thứ $i$ của $x$ khác nhau, chữ số của $y$ phải nhỏ hơn $s[i]$.
Từ nhận xét này, ta xét các vị trí $i$ từ $0$ đến $n - 1$, mỗi $i$ ứng với một nhóm số $y$ có dạng:
Khi này số $y$ nhận được sẽ gồm các chữ số của phần đầu $s[0 \ldots i-1]$ và các chữ số của $g$. Nhìn kĩ hơn ta thấy được rằng chữ số lớn nhì của $y$ chắc chắn nằm trong 4 chữ số: lớn nhất, lớn nhì của phần đầu và lớn nhất, lớn nhì của $g$. Ta lần lượt đặt:
- $mx$ là chữ số lớn nhất của $s[0 \ldots i-1]$; $mx\_$ là chữ số lớn nhì của $s[0 \ldots i-1]$.
- $e$ là chữ số lớn nhất của $g$; $m$ là chữ số lớn nhì của $g$.
Sẽ có 4 trường hợp sau (chúng rời nhau và phủ hết mọi khả năng):
| Lớn nhì của $y$ là | Điều kiện | Cần biết gì về các xâu $g$ thoả mãn | Kết quả cộng thêm | Mảng |
|---|---|---|---|---|
| $mx$ | $e \ge mx$ và $m \le mx$ | số lượng xâu, gọi là $cnt_1$ | $cnt_1 \times mx$ | sl |
| $e$ | $mx \gt e$ và $mx\_ \le e$ | tổng các chữ số lớn nhất $e$, gọi là $S_e$ | $S_e$ | big |
| $mx\_$ | $mx\_ \gt e$ | số lượng xâu, gọi là $cnt_2$ | $cnt_2 \times mx\_$ | sl_ |
| $m$ | $m \gt mx$ | tổng các chữ số lớn nhì $m$, gọi là $S_m$ | $S_m$ | sml |
Ví dụ: phần đầu là $\underline{5}\,\underline{2}$ ($mx = 5$, $mx\_ = 2$). Nếu $g = 71$ thì $e = 7 \ge 5$, $m = 1 \le 5$ → lớn nhì là $mx = 5$ (số $5271$: giảm dần $7, 5, 2, 1$ ✔). Nếu $g = 33$ thì $5 \gt e = 3 \ge 2$ → lớn nhì là $e = 3$. Nếu $g = 10$ thì $mx\_ = 2 \gt e = 1$ → lớn nhì là $mx\_ = 2$. Nếu $g = 86$ thì $m = 6 \gt 5$ → lớn nhì là $m = 6$.
Các mảng quy hoạch động
Ta sẽ có các mảng sau để thực hiện tính toán (với $len$ là độ dài xâu $g$, $dig$ là chữ số bắt đầu, $(j, g)$ đóng vai trò $(mx, mx\_)$ của phần đầu):
sl[len][dig][j][g]: số cách tạo một xâu có $len$ chữ số, chữ số bắt đầu là $\le dig$ (có thể là số $0$), thoả mãn điều kiện trường hợp 1 với $mx = j$, $mx\_ = g$.big[len][dig][j][g]: tổng các chữ số lớn thứ nhất của các xâu có $len$ chữ số, chữ số bắt đầu $\le dig$, thoả mãn điều kiện trường hợp 2.sl_[len][dig][j][g]: số cách tạo xâu như trên thoả mãn điều kiện trường hợp 3.sml[len][dig][j][g]: tổng các chữ số lớn thứ nhì của các xâu như trên thoả mãn điều kiện trường hợp 4.
Lý do ta phải quản lý trạng thái chữ số bắt đầu (và cộng dồn theo $dig$ để có "$\le dig$") là vì chữ số thứ $i$ điền vào cần nhỏ hơn $s[i]$: khi tính nhóm $i$ ta chỉ việc tra sl[len][s[i] - 1][mx][mx_],… là ra ngay đóng góp của cả nhóm.
Để tính các mảng kia, ta sẽ sử dụng một mảng tính toán nữa là f[len][dig][e][m]: số cách tạo một xâu có $len$ chữ số (có thể có chữ số $0$ ở đầu), chữ số bắt đầu là $dig$, có $e$ là chữ số lớn nhất, $m$ là chữ số lớn nhì. Ta sẽ sử dụng quy hoạch động chữ số để dễ dàng tính mảng này: từ một xâu độ dài $i$ ở trạng thái $(j, g, k)$, thêm một chữ số $dig$ vào cuối thì trạng thái mới được cập nhật y như cách cập nhật mx, mx_ ở subtask 1:
dig >= g → $(j, dig, g)$; ngược lại dig >= k → $(j, g, dig)$; còn lại → $(j, g, k)$ (cộng dồn f[i + 1][...] += f[i][j][g][k]).Rồi tính các mảng kết quả bằng cách xét hết tất cả các cặp $(e, m)$:
- Nếu $e \ge j$ và $m \le j$ thì
sl[len][dig][j][g] += f[len][dig][e][m]. - Nếu $j \gt e$ và $g \le e$ thì
big[len][dig][j][g] += f[len][dig][e][m] * e. - Nếu $g \gt e$ thì
sl_[len][dig][j][g] += f[len][dig][e][m]. - Nếu $m \gt j$ thì
sml[len][dig][j][g] += f[len][dig][e][m] * m.
Nhóm đầu tiên ($i = 0$) và chữ số cuối
Tuy nhiên, nếu $i = 0$ (chưa có phần đầu nào), áp dụng phía trên sẽ tạo ra sai sót vì khi $c = 0$ thì $y$ có thể có các chữ số $0$ ở đầu, và $f$ sẽ bị tác dụng bởi những số $0$ đó (ví dụ "$05$" sẽ bị tính lớn nhì là $0$ như thể có 2 chữ số, trong khi $5$ chỉ có 1 chữ số). Ta cần lớn nhì của $y$ không bị ảnh hưởng bởi các số $0$ ở đầu. Để xử lý điều này, chúng ta chỉ cần tạo một mảng quy hoạch động khác d[len][tt][dig][e][m] thêm một trạng thái là $tt$, với $tt = 0$ là còn toàn các số $0$ ở đầu, còn $tt = 1$ là đã xuất hiện chữ số khác $0$. Vì ở $i = 0$ không tồn tại phần đầu nên kết quả chỉ phụ thuộc vào số lớn nhì của $g$. Do đó, ta gọi sum[len][dig] là tổng chữ số lớn nhì của các số $len$ chữ số (cho phép số $0$ ở đầu để biểu diễn các số ngắn hơn) sao cho chữ số bắt đầu $\le dig$; vậy nhóm $i = 0$ đóng góp đúng sum[n][s[0] - 1]. Các số có 1 chữ số (như "$05$") có lớn nhì bằng $0$ nên không ảnh hưởng tổng.
Với $i = 1$ thì phần đầu mới có đúng 1 chữ số, chưa có $mx\_$ (code để mx_ = -1). Khi đó ta tra bảng với $mx\_ = 0$ ([mx][mx_ + 1]) và bỏ qua trường hợp 3 – vì $g$ có ít nhất 2 chữ số nên coi thêm một chữ số $0$ cũng không làm thay đổi chữ số lớn nhì. Còn nếu $s[i] = 0$ thì không có chữ số $c \lt 0$ nào, nhóm đó rỗng.
Cuối cùng, ở vị trí cuối $i = n - 1$ chỉ còn đúng 1 chữ số tự do, ta duyệt trực tiếp $j = 0, 1, \ldots, s[n-1]$ (lấy cả $j = s[n-1]$, tức là chính số $x$) và cộng chữ số lớn nhì của từng số vào.
Khung minh hoạ dưới đây chia các số từ $0$ đến $x$ thành từng nhóm đúng như trên và tính đóng góp từng nhóm theo 4 trường hợp (với $x$ nhỏ thì khung còn cộng trâu để đối chiếu):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, l, r;
int MOD = 7 * 1e9 + 1;
int sl[20][10][10][10];
int sml[20][10][10][10];
int big[20][10][10][10];
int sl_[20][10][10][10];
int f[20][10][10][10];
int d[20][2][10][10][10];
int sum[20][10];
int que(int x){
if (x < 10) return 0;
string s = to_string(x);
int res = 0;
int mx = -1, mx_ = -1;
for (int i = 0; i < s.size() - 1; i ++){
if (mx == -1 && mx_ == -1){
res += sum[s.size() - i][s[i] - 49];
res %= MOD;
}
else if (mx_ == -1){
if (s[i] - 48){
res += sl[s.size() - i][s[i] - 49][mx][mx_ + 1] * mx;
res %= MOD;
res += big[s.size() - i][s[i] - 49][mx][mx_ + 1];
res += sml[s.size() - i][s[i] - 49][mx][mx_ + 1];
}
}
else{
if (s[i] - 48){
res += (sl[s.size() - i][s[i] - 49][mx][mx_]) * mx;
res += (big[s.size() - i][s[i] - 49][mx][mx_]);
res += sml[s.size() - i][s[i] - 49][mx][mx_];
res += sl_[s.size() - i][s[i] - 49][mx][mx_] * mx_;
res %= MOD;
}
}
if (s[i] - 48 >= mx){
mx_ = mx;
mx = s[i] - 48;
}
else if (s[i] - 48 >= mx_){
mx_ = s[i] - 48;
}
}
for (int j = 0; j <= s[s.size() - 1] - 48; j ++){
int g = mx, m = mx_;
if (j >= g){
m = g;
g = j;
}
else if (j >= m){
m = j;
}
res += m;
}
return res;
}
signed main(){
if(fopen("SECOND.inp", "r")){
freopen("SECOND.inp", "r", stdin);
freopen("SECOND.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
f[0][0][0][0] = 1;
for (int i = 0; i < 19; i ++){
for (int j = 0; j < 10; j ++){
for (int g = 0; g < 10; g ++){
for (int k = 0; k < 10; k ++){
for (int dig = 0; dig < 10; dig ++){
if (!f[i][j][g][k]) continue;
if (i == 0) f[i + 1][dig][dig][0] += f[i][j][g][k];
else{
if (dig >= g) f[i + 1][j][dig][g] += f[i][j][g][k];
else if (dig >= k) f[i + 1][j][g][dig] += f[i][j][g][k];
else f[i + 1][j][g][k] += f[i][j][g][k];
}
}
}
}
}
}
d[0][0][0][0][0] = 1;
for (int i = 0; i < 19; i ++){
for (int tt = 0; tt <= 1; tt ++){
for (int j = 0; j < 10; j ++){
for (int g = 0; g < 10; g ++){
for (int k = 0; k < 10; k ++){
for (int dig = 0; dig < 10; dig ++){
if (!d[i][tt][j][g][k]) continue;
if (!tt && dig == 0){
d[i + 1][0][0][0][0] = d[i][0][0][0][0];
continue;
}
if (i == 0) d[i + 1][1][dig][dig][0] += d[i][tt][j][g][k];
else if (!tt) d[i + 1][1][j][dig][0] += d[i][tt][j][g][k];
else{
if (dig >= g){
d[i + 1][1][j][dig][g] += d[i][tt][j][g][k];
}
else if (dig >= k){
d[i + 1][1][j][g][dig] += d[i][tt][j][g][k];
}
else{
d[i + 1][1][j][g][k] += d[i][tt][j][g][k];
}
}
}
}
}
}
}
}
for (int i = 2; i <= 19; i ++){
for (int dig = 0; dig < 10; dig ++){
if (dig) sum[i][dig] += sum[i][dig - 1];
for (int g = 0; g < 10; g ++){
for (int k = 0; k < 10; k ++){
sum[i][dig] += (d[i][1][dig][g][k] % MOD) * k;
}
}
sum[i][dig] %= MOD;
}
}
for (int i = 2; i <= 19; i ++){
for (int dig = 0; dig < 10; dig ++){
for (int j = 0; j < 10; j ++){
for (int g = 0; g < 10; g ++){
if (dig){
sl[i][dig][j][g] += sl[i][dig - 1][j][g];
big[i][dig][j][g] += big[i][dig - 1][j][g];
sml[i][dig][j][g] += sml[i][dig - 1][j][g];
sl_[i][dig][j][g] += sl_[i][dig - 1][j][g];
}
for (int e = 0; e < 10; e ++){
for (int m = 0; m < 10; m ++){
if (e >= j && m <= j) sl[i][dig][j][g] += f[i][dig][e][m];
if (j > e && g <= e) big[i][dig][j][g] += (f[i][dig][e][m] * e) % MOD;
if (g > e) sl_[i][dig][j][g] += f[i][dig][e][m];
if (m > j) sml[i][dig][j][g] += (f[i][dig][e][m] * m) % MOD;
}
}
sl[i][dig][j][g] %= MOD;
big[i][dig][j][g] %= MOD;
sml[i][dig][j][g] %= MOD;
sl_[i][dig][j][g] %= MOD;
}
}
}
}
while (t --){
cin >> l >> r;
cout << ((que(r) % MOD) - (que(l - 1) % MOD) + MOD) % MOD << '\n';
}
}import sys
MOD = 7 * 10**9 + 1
R = range(10)
def build():
# f[i][j][g][k]: số xâu độ dài i (cho phép số 0 ở đầu), chữ số đầu j,
# chữ số lớn nhất g, lớn nhì k
f = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
for dig in R:
f[1][dig][dig][0] = 1
for i in range(1, 19):
for j in R:
for g in R:
for k in R:
c = f[i][j][g][k]
if not c:
continue
for dig in R:
if dig >= g: f[i + 1][j][dig][g] += c
elif dig >= k: f[i + 1][j][g][dig] += c
else: f[i + 1][j][g][k] += c
# d[i][tt][j][g][k]: như f nhưng bỏ qua các số 0 ở đầu (tt = 1: đã gặp chữ số khác 0)
d = [[[[[0] * 10 for _ in R] for _ in R] for _ in range(2)] for _ in range(20)]
d[0][0][0][0][0] = 1
for i in range(19):
for tt in range(2):
for j in R:
for g in R:
for k in R:
c = d[i][tt][j][g][k]
if not c:
continue
for dig in R:
if not tt and dig == 0:
d[i + 1][0][0][0][0] = d[i][0][0][0][0]
continue
if i == 0: d[i + 1][1][dig][dig][0] += c
elif not tt: d[i + 1][1][j][dig][0] += c
elif dig >= g: d[i + 1][1][j][dig][g] += c
elif dig >= k: d[i + 1][1][j][g][dig] += c
else: d[i + 1][1][j][g][k] += c
sm = [[0] * 10 for _ in range(20)]
for i in range(2, 20):
for dig in R:
v = sm[i][dig - 1] if dig else 0
for g in R:
for k in R:
v += d[i][1][dig][g][k] * k
sm[i][dig] = v % MOD
sl = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
big = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
sml = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
sl_ = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
for i in range(2, 20):
for dig in R:
items = [(e, m, f[i][dig][e][m]) for e in R for m in R if f[i][dig][e][m]]
for j in R:
for g in R:
a = b = c = e_ = 0
if dig:
a = sl[i][dig - 1][j][g]; b = big[i][dig - 1][j][g]
c = sml[i][dig - 1][j][g]; e_ = sl_[i][dig - 1][j][g]
for e, m, cnt in items:
if e >= j and m <= j: a += cnt
if j > e and g <= e: b += cnt * e
if g > e: e_ += cnt
if m > j: c += cnt * m
sl[i][dig][j][g] = a % MOD; big[i][dig][j][g] = b % MOD
sml[i][dig][j][g] = c % MOD; sl_[i][dig][j][g] = e_ % MOD
# Gộp sẵn phần đóng góp cho từng trạng thái (mx = j, mx_ = g) để mỗi truy vấn chỉ tra bảng:
# A: khi phía trước mới có 1 chữ số (mx_ = -1, coi như 0, không có phần sl_)
# B: trường hợp tổng quát (có thêm sl_ * mx_)
A = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
B = [[[[0] * 10 for _ in R] for _ in R] for _ in range(20)]
for i in range(2, 20):
for dig in R:
for j in R:
for g in R:
v = sl[i][dig][j][g] * j + big[i][dig][j][g] + sml[i][dig][j][g]
A[i][dig][j][g] = v % MOD
B[i][dig][j][g] = (v + sl_[i][dig][j][g] * g) % MOD
return sm, A, B
def que(x, T):
sm, A, B = T
if x < 10:
return 0
s = str(x); n = len(s)
res = 0
mx = mx_ = -1
for i in range(n - 1):
c = ord(s[i]) - 48
L = n - i
if mx == -1:
res += sm[L][c - 1]
elif c:
if mx_ == -1:
res += A[L][c - 1][mx][0]
else:
res += B[L][c - 1][mx][mx_]
if c >= mx:
mx_ = mx; mx = c
elif c >= mx_:
mx_ = c
for j in range(ord(s[-1]) - 47):
g, m = mx, mx_
if j >= g:
m = g; g = j
elif j >= m:
m = j
res += m
return res % MOD
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
T = build()
out = []
for q in range(t):
l = int(data[1 + 2 * q]); r = int(data[2 + 2 * q])
out.append((que(r, T) - que(l - 1, T)) % MOD)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Giải thích 1 số chỗ trong code ở trên:
s[i] - 48là giá trị chữ số $s[i]$ (mã ASCII của'0'là $48$), còns[i] - 49là $s[i] - 1$: chữ số lớn nhất được phép điền ở vị trí $i$.#define int long longvàMOD = 7 * 1e9 + 1: số lượng xâu dài 19 chữ số lên tới cỡ $10^{18}$ nên mảngf,dphải làlong long(và không lấy dư, vì vẫn vừa). Các mảngsl,big,sml,sl_,sumthì lấy dư cho $7 \cdot 10^9 + 1$ – để ý số chia này lớn hơn $2^{31}$ nên cũng phải dùnglong long.- Kết quả cuối
((que(r) % MOD) - (que(l - 1) % MOD) + MOD) % MOD: cộng thêmMODđể tránh ra số âm khi lấy hiệu hai số đã chia dư. - Bản Python gộp sẵn phần đóng góp
sl * mx + big + sml (+ sl_ * mx_)vào 2 bảngA,Bđể mỗi truy vấn chỉ tra 1 ô cho mỗi chữ số, cho đỡ chậm; công thức y hệt bản C++.
Khung chạy tay dưới đây gom phần tính trước các bảng (4 vòng lặp lồng nhau rất dài) thành vài bước, còn hàm que thì chạy chi tiết từng dòng. Để số trong JavaScript vẫn chính xác, em nhập $r \lt 10^{15}$ nhé:
Đánh giá độ phức tạp của cách làm này:
- Không gian: các mảng QHĐ cỡ $20 \times 10^3$ (riêng
dlà $20 \times 2 \times 10^3$) phần tử – rất nhỏ, coi như $O(1)$. - Thời gian: phần tính trước khoảng $19 \times 10^4$ phép tính cho
f,dvà $18 \times 10^4$ phép tính cho các mảngsl,big,… (không phụ thuộc dữ liệu). Mỗi truy vấn gọique2 lần, mỗi lần duyệt qua tối đa 18 chữ số và 10 giá trị cuối: $O(19)$. Tổng $O(t \cdot 19)$.
freopen trực tiếp, ở đây mình bọc thêm if(fopen(...)) để nộp trên web không bị lỗi.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét