Cộng một kiểu Đức
Đề bài
Đức vừa phát minh ra một phép toán cộng độc đáo và đặt tên cho nó là “cộng một kiểu Đức”, cách cộng như sau: Mỗi lần cộng một số nguyên cho một thay vì tăng giá trị của số đó lên một đơn vị, Đức lại tăng tất cả các chữ số của số đó lên một đơn vị.
Ví dụ 1: $15$ “cộng một kiểu Đức” sẽ cho kết quả là $26$.
Ví dụ 2: $91$ “cộng một kiểu Đức” sẽ cho kết quả là $102$.
Yêu cầu: Với $T$ số nguyên dương $N$ cho trước hãy tính toán và cho biết sau khi thực hiện $K$ lần phép cộng một kiểu Đức thì kết quả sinh ra có bao nhiêu chữ số. Vì câu trả lời có thể rất lớn do đó hãy in ra kết quả sau khi chia lấy dư cho $10^9 + 7$.
Dữ liệu vào:
- Dòng thứ nhất: chứa số nguyên $T$ $(1 \le T \le 2 \cdot 10^5)$.
- $T$ dòng tiếp theo mỗi dòng chứa 2 số nguyên lần lượt là $N$ và $K$ $(1 \le N \le 10^9;\ 1 \le K \le 2 \cdot 10^5)$.
Kết quả: Với mỗi trường hợp in ra số lượng chữ số của kết quả chia lấy dư cho $10^9 + 7$.
Scoring
- Có $30\%$ test với $T \le 10,\ K \le 20$;
- Có $20\%$ test với $T \le 100,\ K \le 50$;
- Có $50\%$ test không có giới hạn gì thêm.
2
9812 2
9899 36
8Note:
- $9812 \to 10923 \to 211034$ (6 chữ số)
- $9899 \to 1091010 \to 21102121 \to 32213232$ (8 chữ số)
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn bằng chuỗi – 50% test
Theo quy luật như đề bài đưa ra thì khá dễ dàng để làm được code vét cạn em ha, và ít nhất nó sẽ lấy được 2 subtask đầu tiên tức là $50\%$ điểm. Cũng như ta có thể lợi dụng nó làm tool test cho cách tối ưu (sinh test ngẫu nhiên nhỏ, so kết quả 2 code với nhau).
Ý tưởng code vét cạn thì đơn giản là làm theo đúng như mô tả yêu cầu đề thôi: cho vòng lặp chạy $T$ lần, mỗi lần đọc dữ liệu số $n$ và $k$ thì đối với số $n$ ta nên đọc vào ở dạng chuỗi để từ đó việc xét từng ký tự số sẽ dễ dàng, chứ nếu dùng kiểu số thì sẽ phải phức tạp vấn đề lên. Khi xét từng ký tự số:
- Nếu nó không phải ký tự
'9'thì ta cứ++lên thôi. - Còn nếu là ký tự
'9'thì sẽ biến nó lại thành ký tự'1'và theo lẽ thì phải có ký tự'0'được thêm vào ngay sau ký tự'1'đó.
Nhưng bản chất nếu làm vậy thì sẽ tăng độ phức tạp lên, vì chi phí thêm 1 phần tử vào giữa chuỗi (bản chất là mảng) sẽ là $O(\text{Length})$. Trong khi đó ta thấy rõ ràng dù 9 biến thành 10 rồi thì khi cộng tiếp các lần sau thì nó cũng cộng riêng lẻ cho ký tự 1 rồi riêng cho ký tự 0, chúng không bị phụ thuộc vào nhau. Vì thế ký tự 0 không nhất thiết phải nằm ngay sau ký tự 1, mà ta nên thêm nó vào sau cùng của chuỗi, như thế chỉ mất chi phí $O(1)$ sẽ tốt hơn. Rồi thì lặp lại quy trình cộng liên tục $k$ lần và sau đó thì in kết quả độ dài của chuỗi, nhớ chia dư cho $10^9 + 7$ như đề bài yêu cầu.
| k | Số thật | Chuỗi trong code | Dài |
|---|---|---|---|
| 0 | 9899 | 9899 | 4 |
| 1 | 1091010 | 1911000 | 7 |
| 2 | 21102121 | 21221110 | 8 |
| 3 | 32213232 | 32332221 | 8 |
Ô cam = chữ số 0 mới được push_back vào cuối. Thứ tự chữ số khác số thật nhưng số lượng chữ số luôn bằng nhau – mà đề chỉ hỏi số lượng.
Source code sẽ như sau em tham khảo nhé:
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
string s;
int k;
cin >> s >> k;
while(k--){
int length = s.length();
for(int i = 0; i < length; ++i){
if(s[i] < '9'){
s[i]++;
}
else{
s[i] = '1';
s.push_back('0');
}
}
}
cout << s.length() % m << '\n';
}
return 0;
}import sys
m = 10**9 + 7
data = sys.stdin.read().split()
t = int(data[0])
out = []
for q in range(t):
s = list(data[1 + 2 * q])
k = int(data[2 + 2 * q])
for _ in range(k):
length = len(s)
for i in range(length):
if s[i] < '9':
s[i] = chr(ord(s[i]) + 1)
else:
s[i] = '1'
s.append('0') # thêm '0' vào cuối cho nhanh, thứ tự không ảnh hưởng số chữ số
out.append(len(s) % m)
print('\n'.join(map(str, out)))Để ý biến length được lấy trước vòng for: các chữ số 0 vừa được push_back trong lần cộng này sẽ không bị cộng thêm ngay trong cùng lần đó.
Độ phức tạp thời gian sẽ là $O(T \cdot K \cdot \text{Length})$, và rõ ràng nội việc chỉ cần $T \cdot K$ thì bài đó $T, K$ tối đa là $2 \cdot 10^5$, như vậy $T \cdot K = 4 \cdot 10^{10}$ tức là 40 tỷ, đã vượt quá ngưỡng giới hạn thời gian chạy cho 1 giây (tối đa chỉ khoảng 100 triệu phép tính). Tuy nhiên cái đáng sợ hơn là cái $\text{Length}$, vì nó sẽ là 1 con số rất khủng khiếp nếu rơi vào trường hợp xấu. Để anh sẽ cho em thấy:
Chuỗi dài khủng khiếp cỡ nào?
Nếu như dùng chuỗi là dở vì chuỗi sinh ra có thể sẽ rất dài, thì sợ rằng memory lưu không nổi luôn đó chứ. Vì em ngẫm thử 1 trường hợp xấu mà anh giả sử này nhé:
- Giả sử $n$ ban đầu $= 999999999$ (9 chữ số 9), vậy thì sau 1 lần cộng sẽ tạo ra 18 chữ số:
101010101010101010. - Tiếp tục sau 9 lần cộng nữa thì 9 con số
1sẽ tạo ra thêm 9 con số mới. - Rồi thêm 1 lần cộng nữa thì 9 con số
0sẽ tạo ra thêm 9 con số mới. - Nên mình có thể hiểu là: cứ sau 1 (lần ban đầu) + 9 + 1 = 11 lần thì sẽ gấp đôi thành 36 chữ số; rồi sau 11 lần nữa thì lại gấp đôi thành 72 chữ số; rồi 144 chữ số…
Nếu không tin thì em thử chạy đoạn code vét cạn ở trên với các test 1 / 999999999 11 sẽ thấy kết quả là 36, 999999999 22 ra 72, 999999999 33 ra 144, 999999999 44 ra 288. Nó cứ thế nhân 2 lên liên tục em hình dung được không?
Mà em nhìn xem: $K$ đề cho tối đa là $2 \cdot 10^5$, vậy sẽ có $K / 11 \approx 18181$ lần gấp đôi (18 ngàn 181 lần). Nghĩa là kết quả sau cùng chuỗi sẽ có độ dài là khoảng $18 \cdot 2^{18181}$, quá lớn rồi đó em. Lũy thừa $2^{30}$ đã là hơn 1 tỷ rồi; kiểu số nguyên lớn nhất mà C++ hỗ trợ sẵn là kiểu 8 byte (64 bit) thì tối đa nó lưu được cỡ $2^{64}$, trong khi ở đây là cần đến số mũ 18 ngàn 181. Chưa kể là chuỗi sinh ra lại phải duyệt vòng lặp vào từng ký tự để ++ lên. Đó, nếu dùng chuỗi là thua: memory lưu không nổi, time chạy cũng không nổi.
Cách 2Mảng đếm 10 chữ số – O(T·K·10)
Mấu chốt em có độ phức tạp cao như vậy là bởi vì em sử dụng chuỗi. Em phải nghĩ theo hướng không dùng chuỗi thì mới tối ưu nhé: thực tế chỉ cần dùng mảng đánh dấu có 10 phần tử tương ứng từ 0 đến 9. Ví dụ mảng a thì a[i] sẽ lưu số lượng chữ số $i$, ví dụ a[3] sẽ lưu số lượng chữ số 3. Nếu số tạo ra có 100 chữ số 1, thay vì em tạo ra chuỗi "1111...111" (100 số 1) thì em chỉ cần thống kê tại index 1 mang giá trị 100, tức là a[1] = 100. Làm như thế thì em sẽ không phải lưu trữ quá nhiều và phải duyệt quá nhiều.
Sau 1 lần cộng, số lượng chữ số $d$ ($d < 9$) chuyển hết sang thành chữ số $d + 1$; còn số lượng chữ số 9 thì mỗi chữ số 9 biến thành 10, tức là góp vào cả số lượng chữ số 1 lẫn chữ số 0:
Rồi sau cùng thì khi duyệt số lượng các chữ số để cộng tổng lại thì đó là đáp án. Thay vì cộng tổng lại hết rồi ta mới chia lấy dư thì ta sẽ áp dụng đồng dư thức $(a + b) \bmod c$ $= ((a \bmod c) + (b \bmod c)) \bmod c$, từ đó cứ mỗi lần cộng vào là ta chia lấy dư luôn để tránh trường hợp bị tràn số do quá lớn.
Em nhập $N$, $K$ rồi bấm Tiếp để xem cùng lúc số thật và mảng đếm biến đổi qua từng lần cộng:
Source code sẽ như sau:
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> a(10, 0);
while(n != 0){
a[n % 10]++;
n /= 10;
}
while(k--){
vector<int> b(10, 0);
for(int i = 0; i < 9; ++i){
b[i + 1] = a[i];
}
b[1] += a[9];
b[0] += a[9];
a = b;
}
int res = 0;
for(int i = 0; i < 10; ++i){
res += a[i] % m;
res %= m;
}
cout << res << '\n';
}
return 0;
}import sys
m = 10**9 + 7
data = sys.stdin.read().split()
t = int(data[0])
out = []
for q in range(t):
n = int(data[1 + 2 * q])
k = int(data[2 + 2 * q])
a = [0] * 10 # a[d] = số lượng chữ số d
while n != 0:
a[n % 10] += 1
n //= 10
for _ in range(k):
b = [0] * 10
for i in range(9):
b[i + 1] = a[i]
b[1] += a[9]
b[0] += a[9]
a = b
out.append(sum(a) % m)
print('\n'.join(map(str, out)))Độ phức tạp thời gian giờ đây chỉ là $O(T \cdot K \cdot 10)$. Rõ ràng nó tốt hơn rất nhiều so với cách làm trước đó khi độ phức tạp là $O(T \cdot K \cdot \text{Length})$ với $\text{Length}$ là 1 con số rất khủng khiếp, thì giờ đây $\text{Length}$ đã thay bằng số 10. Tuy nhiên thì như đã nói $T, K$ tối đa là $2 \cdot 10^5$ nên $T \cdot K = 4 \cdot 10^{10}$, giờ tiếp tục nhân thêm 10 nữa thì thành 400 tỷ. Trong khi đó ngưỡng giới hạn 1 giây là 100 triệu, vì thế chắc chắn code này tuy tối ưu hơn nhưng vẫn sẽ bị TLE. Dù sao thì cũng rất đáng khen ngợi khi từ code trước đó ta tối ưu ra code này, vì trường hợp xấu nhất anh đề ra đó, nếu như code trước đó chắc là đến khi trái đất tận thế cũng chưa ra kết quả, còn với code này thì chỉ mất $400$ tỷ $/ 100$ triệu $= 4000$ giây, hơn 1 giờ là ra kết quả rồi 😄.
a[i], b[i] là int và không được chia dư trong lúc lặp, nên khi $K$ lớn (số chữ số tăng theo cấp số nhân, cỡ $2^{K/11}$) thì sẽ bị tràn số. Ví dụ test 1 / 999999999 200000 code này in ra số âm -212862980 thay vì 831614621. Ở 2 subtask đầu ($K \le 50$) thì không sao. Muốn an toàn em chỉ cần sửa 2 dòng thành b[1] = (b[1] + a[9]) % m; và b[0] = (b[0] + a[9]) % m; (giống như cách mod trong Cách 3).Nhưng ta sẽ cần tìm ra cách tối ưu để đảm bảo ra được kết quả trong tối đa 1 giây. Hãy tiếp tục xem nhé:
Cách 3Bảng thống kê theo từng chữ số và từng K – AC
Mấu chốt của bài này là nhận ra như sau: ví dụ số $n$ có dạng abcde và cần đếm xem sau $k$ lần cộng sẽ có bao nhiêu chữ số theo quy tắc đề bài đưa ra. Thì sẽ hiểu là:
- Đếm xem chữ số
asau $k$ lần cộng sẽ tạo ra bao nhiêu chữ số; - Đếm xem chữ số
bsau $k$ lần cộng sẽ tạo ra bao nhiêu chữ số; - … tương tự với
c,d,e.
Cộng tổng lại thì đó là đáp án (vì các chữ số biến đổi độc lập với nhau, như đã thấy ở Cách 1).
Vấn đề là có $T$ test case, mỗi test case thì $N$ trong đoạn $[1, 10^9]$, $K$ trong đoạn $[1, 2 \cdot 10^5]$, thì nhận thấy mấu chốt chỉ là xét các chữ số của số $N$ thôi, và ta biết chỉ có 10 chữ số từ 0 đến 9, $K$ thì cũng chỉ trong đoạn từ 1 đến $2 \cdot 10^5$. Nên là ta tạo bảng thống kê:
- Ứng với từng chữ số (từ 0 đến 9),
- Ứng với từng giá trị $k$ (từ 1 đến $2 \cdot 10^5$),
- Thì xem coi chữ số đó, sau $k$ lần cộng, sẽ tạo ra bao nhiêu chữ số?
Khi có được bảng thống kê rồi thì với từng test case, với số $n$ ta lấy ra từng chữ số của nó, gọi vào chữ số tương ứng trong bảng thống kê và tại vị trí $k$ tương ứng, ta biết được chữ số đó sau $k$ lần cộng sẽ tạo ra bao nhiêu chữ số mới, rồi cộng tổng lại với toàn bộ các chữ số của $n$ là ra đáp án sau cùng.
Chi phí tạo bảng: ta có 10 chữ số, với 1 chữ số thì xét qua $2 \cdot 10^5$ cái $K$, và áp dụng tư tưởng dùng mảng đánh dấu thay vì chuỗi như ở trên thì mỗi cái $K$ sẽ xét qua mảng đánh dấu có 10 phần tử. Vậy $10 \cdot 2 \cdot 10^5 \cdot 10 = 2 \cdot 10^7$, nhỏ hơn ngưỡng $10^8$ nên vẫn ổn nè.
Ví dụ chữ số 9 đi ha: $9 \to 10 \to 21 \to 32 \to \ldots \to 98 \to 109 \to 2110 \to 3221 \to 4332$. Đó thì em cứ tạo bảng thống kê cho đến $+\,2 \cdot 10^5$. Và không nên lưu theo dạng chuỗi vì như anh đã nói nó sẽ có độ phức tạp cực kỳ lớn cả về thời gian lẫn bộ nhớ, hãy dùng mảng đánh dấu có 10 phần tử để lưu số lượng các chữ số thôi:
| k | 9 sau k lần | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Tổng |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 10 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 2 | 21 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3 | 32 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 4 | 43 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 2 |
| 5 | 54 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 2 |
| 6 | 65 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 2 |
| 7 | 76 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 2 |
| 8 | 87 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 2 |
| 9 | 98 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 |
| 10 | 109 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 3 |
| 11 | 2110 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 |
| 12 | 3221 | 0 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 4 |
| 13 | 4332 | 0 | 0 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 4 |
Ví dụ số 9: trước khi cộng thì mảng đánh dấu của nó là 0, 0, 0, 0, 0, 0, 0, 0, 0, 1. Sau khi cộng 1 lần thành 10 thì số lượng chữ số 9 mất đi, thay vào đó số lượng chữ số 9 đó được cộng vào vị trí chữ số 0 và 1, ta có mảng đánh dấu là 1, 1, 0, 0, 0, 0, 0, 0, 0, 0. Nhìn dòng cuối cùng: $9$ cộng 13 lần $= 4332$ nên a[9][13] sẽ là mảng đánh dấu có 1 số 2, 2 số 3, 1 số 4, nghĩa là a[9][13] = {0, 0, 1, 2, 1, 0, 0, 0, 0, 0}.
int a[10][200001][10]a[i][k][j] = số lượng chữ số $j$ sinh ra từ chữ số $i$ sau $k$ lần cộng.• Số 10 đầu tiên: các chữ số $i$ từ 0 đến 9.
• Số 200001: $k$ từ 0 đến $2 \cdot 10^5$.
• Số 10 cuối: mảng đánh dấu 10 phần tử (chữ số $j$).
Công thức chuyển y như Cách 2:
a[i][k][j] = a[i][k-1][j-1] với $j = 1..9$, rồi a[i][k][0] += a[i][k-1][9], a[i][k][1] += a[i][k-1][9].Tạo ra được cái bảng này chỉ mất $10 \cdot 2 \cdot 10^5 \cdot 10 = 2 \cdot 10^7$ thôi, vẫn ổn. Rồi khi có nó rồi là xong, khỏe: với mỗi số $n$, lấy từng chữ số, với từng chữ số sẽ biết ngay chữ số ấy sau khi trải qua $K$ lần sẽ tạo ra bao nhiêu chữ số khác, cứ cộng tổng lại là xong.
Tuy nhiên lưu ý em rằng nhớ cái vụ mod $10^9 + 7$ thì nên mod ngay từ lúc tạo mảng 3 chiều và mod thêm lúc cộng tổng các chữ số của $N$. Như vậy bước sau đó chỉ cần xét qua toàn bộ chữ số của số $N$ là ra kết quả. Mà ta biết $N$ tối đa có 10 chữ số ($N \le 10^9$), $T$ tối đa $2 \cdot 10^5$ nên khúc sau cũng chỉ cần lặp $2 \cdot 10^5 \cdot 10 \cdot 10 = 2 \cdot 10^7$ lần là xong.
Source code làm theo đúng tư tưởng anh đã nói đó và đã nộp AC full 100% trên web em xem nhé:
#include <bits/stdc++.h>
using namespace std;
int a[10][200001][10];
const int m = 1e9 + 7;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 0; i < 10; ++i){
a[i][0][i] = 1;
}
for(int i = 0; i < 10; ++i){
for(int k = 1; k <= 200000; ++k){
for(int j = 1; j < 10; ++j){
a[i][k][j] = a[i][k - 1][j - 1];
}
a[i][k][0] += a[i][k - 1][9] % m;
a[i][k][0] %= m;
a[i][k][1] += a[i][k - 1][9] % m;
a[i][k][1] %= m;
}
}
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
int res = 0;
while(n != 0){
int x = n % 10;
n /= 10;
for(int j = 0; j < 10; ++j){
res += a[x][k][j];
res %= m;
}
}
cout << res << '\n';
}
return 0;
}import sys
m = 10**9 + 7
MAXK = 200000
# Bảng 3 chiều 10 x 200001 x 10 quá nặng với Python, nên mình chỉ lưu
# tổng số chữ số: total[i][k] = tổng a[i][k][0..9] (cách tính y như C++)
total = [[0] * (MAXK + 1) for _ in range(10)]
for i in range(10):
cur = [0] * 10
cur[i] = 1
total[i][0] = 1
for k in range(1, MAXK + 1):
# b[j] = a[j - 1] (j = 1..9), rồi b[0] += a[9], b[1] += a[9]
c9 = cur[9]
cur = [c9, (cur[0] + c9) % m] + cur[1:9]
total[i][k] = sum(cur) % m
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for q in range(t):
n = int(data[1 + 2 * q])
k = int(data[2 + 2 * q])
res = 0
while n != 0:
res = (res + total[n % 10][k]) % m
n //= 10
out.append(res)
print('\n'.join(map(str, out)))Bảng int a[10][200001][10] chiếm khoảng $2 \cdot 10^7 \cdot 4$ byte $\approx 80$ MB; khai báo toàn cục nên các ô ban đầu đều bằng 0 và không bị tràn stack. Bản Python mình viết thêm không lưu nguyên bảng 3 chiều (quá nặng với Python) mà chỉ lưu tổng số chữ số total[i][k], cách tính y hệt.
Cách 4Thu gọn bảng về 1 chiều (mình viết thêm)
Phần này mình viết thêm cho bạn nào muốn tối ưu tiếp nha 😉. Để ý 2 điều:
- Chữ số $d$ chính là chữ số $0$ sau $d$ lần cộng ($0 \to 1 \to \ldots \to d$). Vậy chữ số $d$ sau $k$ lần cộng = chữ số $0$ sau $k + d$ lần cộng. Chỉ cần 1 hàng của bảng thay vì 10 hàng!
- Gọi
f[k]= số chữ số sinh ra từ chữ số 0 sau $k$ lần cộng. Với $k < 10$ thì chữ số 0 chưa vượt qua 9 nênf[k] = 1. Với $k \ge 10$: sau 10 lần, chữ số 0 thành10, tức là 1 chữ số1và 1 chữ số0, mỗi đứa còn $k - 10$ lần cộng. Chữ số 1 còn $k - 10$ lần = chữ số 0 còn $k - 9$ lần, nên:
Đáp án của 1 test = tổng f[K + d] với mỗi chữ số $d$ của $N$. Kiểm tra với chữ số 9 cộng 13 lần: f[22] = f[12] + f[13] = 2 + 2 = 4, đúng bằng số chữ số của 4332.
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
const int MAXK = 200000 + 10;
int f[MAXK];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// f[k] = số chữ số sinh ra từ chữ số 0 sau k lần cộng
for(int k = 0; k < MAXK; ++k){
if(k < 10){
f[k] = 1;
}
else{
f[k] = (f[k - 10] + f[k - 9]) % m;
}
}
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
int res = 0;
while(n != 0){
int x = n % 10;
n /= 10;
res = (res + f[k + x]) % m;
}
cout << res << '\n';
}
return 0;
}import sys
m = 10**9 + 7
MAXK = 200000 + 10
# f[k] = số chữ số sinh ra từ chữ số 0 sau k lần cộng
f = [1] * MAXK
for k in range(10, MAXK):
f[k] = (f[k - 10] + f[k - 9]) % m
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for q in range(t):
n = int(data[1 + 2 * q])
k = int(data[2 + 2 * q])
res = 0
while n != 0:
res = (res + f[k + n % 10]) % m
n //= 10
out.append(res)
print('\n'.join(map(str, out)))