Tổng Bình Phương Các Số Con
Đề bài
Cho một số nguyên dương $N$ ($1 \le N \le 10^{10^6}$), hãy tính tổng bình phương các số con của số đó.
Số con của một số nguyên dương $N$ là một số được tạo thành bởi một dãy các chữ số liên tiếp của $N$.
Ví dụ với số $N = 2207$ thì kết quả sẽ là:
Kết quả có thể rất lớn nên chỉ cần in ra kết quả chia dư cho $(10^9 + 7)$.
Input: số nguyên dương $N$ ($1 \le N \le 10^{10^6}$).
Output: kết quả tổng bình phương các số con của $N$ chia dư $(10^9 + 7)$.
Subtask
- 20% số test đầu tiên có $N \le 10^{10^2}$.
- 20% số test tiếp theo có $N \le 10^{10^3}$.
- 20% số test tiếp theo có $N \le 10^{10^4}$.
- 20% số test tiếp theo có $N \le 10^{10^5}$.
- 20% số test cuối cùng không có giới hạn gì thêm.
22074963088Nói cách khác, $N$ có thể dài tới $10^6$ chữ số (subtask đầu tiên là tới khoảng 100 chữ số, rồi 1000, $10^4$, $10^5$ chữ số).
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi 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 Codeforces100%Quy hoạch động theo vị trí kết thúc
Nhìn qua đề bài thì thấy có vẻ rất đơn giản đúng không các bạn? Nhưng nếu bạn nào không biết về quy hoạch động trên chữ số thì sẽ không làm nổi bài này đâu, vì $N$ dài tới $10^6$ chữ số thì có khoảng $5 \cdot 10^{11}$ số con, không thể liệt kê hết được. Hướng giải quyết của mình như sau:
Gọi f[i] là tổng bình phương tất cả các số kết thúc tại ký tự N[i]. Ví dụ với $N = 2317$: $f[1] = 2^2$, $f[2] = 3^2 + 23^2$, $f[3] = 1^2 + 31^2 + 231^2$.
Nếu tính f[3] dựa trên f[2], ta sẽ thấy các số tận cùng tại $N[3]$ được tạo nên từ các số tận cùng tại $N[2]$ như sau:
231² = (23 · 10 + 1)² = 23² · 100 + 23 · 20 · 1 + 1²
1² = 1²
Như vậy $f[3] = 100 \cdot f[2]$ $+ 20 \cdot (\text{tổng các số kết thúc tại } N[2]) \cdot N[3]$ $+ 3 \cdot N[3] \cdot N[3]$ (số 3 ở cuối là vì có 3 số kết thúc tại $N[3]$, mỗi số góp một lượng $N[3]^2$). Như vậy, ta cần thêm tổng các số kết thúc tại N[i].
Gọi f1[i] là tổng các số kết thúc tại $N[i]$. Ví dụ $f1[2] = 3 + 23$, $f1[3] = 1 + 31 + 231$. Ta tính f1[3] bởi f1[2]: $f1[3] = f1[2] \cdot 10 + 3 \cdot N[3]$.
f1[i] = f1[i − 1] · 10 + i · N[i]
f[i] = 100 · f[i − 1] + f1[i − 1] · 20 · N[i] + i · N[i] · N[i]
Đáp án bài toán: tổng các
f[i] (mọi phép tính đều lấy modulo $10^9 + 7$).Thử với ví dụ $N = 2207$ (chữ số 0 ở đầu các số con như "07" vẫn được tính bình thường, $07 = 7$):
| i | N[i] | Các số kết thúc tại N[i] | f1[i] | f[i] |
|---|---|---|---|---|
| 1 | 2 | 2 | 0 · 10 + 1 · 2 = 2 | 100 · 0 + 20 · 0 · 2 + 1 · 2² = 4 |
| 2 | 2 | 22, 2 | 2 · 10 + 2 · 2 = 24 | 100 · 4 + 20 · 2 · 2 + 2 · 2² = 488 |
| 3 | 0 | 220, 20, 0 | 24 · 10 + 3 · 0 = 240 | 100 · 488 + 20 · 24 · 0 + 3 · 0² = 48800 |
| 4 | 7 | 2207, 207, 07, 7 | 240 · 10 + 4 · 7 = 2428 | 100 · 48800 + 20 · 240 · 7 + 4 · 7² = 4913796 |
| Đáp án = tổng các f[i] | 4963088 | |||
Vì sao công thức đúng tổng quát? (mình giải thích thêm)
Mỗi số con kết thúc tại $N[i]$ (trừ số chỉ gồm 1 chữ số $N[i]$) có dạng $x \cdot 10 + d$ với $x$ là một số con kết thúc tại $N[i - 1]$ và $d = N[i]$. Ta có $(10x + d)^2$ $= 100x^2 + 20xd + d^2$. Cộng trên tất cả $i - 1$ số $x$ kết thúc tại $N[i - 1]$, rồi cộng thêm số $d$ đứng một mình:
Tương tự, $\sum (10x + d) + d$ $= 10 \cdot f1[i - 1] + (i - 1) d + d$ $= 10 \cdot f1[i - 1] + i \cdot d$.
Mô phỏng: em nhập số $N$ (tối đa 7 chữ số) rồi bấm Tiếp để xem từng bước: ở mỗi chữ số, liệt kê các số con kết thúc tại đó và thấy công thức tính f1[i], f[i] từ cột trước cho ra đúng tổng mà không cần liệt kê:
Độ phức tạp: $O(n)$ với $n$ là số chữ số của $N$, chỉ cần duyệt qua chuỗi 1 lần.
Source code để các bạn tham khảo nếu làm theo những gì mình phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long dp1[1000007];
long long dp[1000007];
string N;
int main(){
cin >> N;
int len = (int)N.size();
dp1[0] = 0;
for(int i = 1; i <= len; i++){
dp1[i] = ((dp1[i - 1] * 10LL) % mod + ((N[i - 1] - '0') * i) % mod) % mod;
}
dp[0] = 0;
for(int i = 1; i <= len; i++){
dp[i] = (dp[i - 1] * 100) % mod;
(dp[i] += (dp1[i - 1] * (N[i - 1] - '0') * 20) % mod) %= mod;
(dp[i] += (N[i - 1] - '0') * (N[i - 1] - '0') * i % mod) %= mod;
}
long long ans = 0LL;
for(int i = 1; i <= len; i++){
(ans += dp[i]) %= mod;
}
cout << ans;
return 0;
}import sys
mod = 1000000007
N = sys.stdin.readline().strip()
dp1 = 0 # f1[i]: tổng các số kết thúc tại N[i]
dp = 0 # f[i]: tổng bình phương các số kết thúc tại N[i]
ans = 0
for i in range(1, len(N) + 1):
d = ord(N[i - 1]) - 48
# f[i] dùng f1[i - 1] nên phải tính f[i] trước khi cập nhật f1
dp = (dp * 100 + dp1 * d * 20 + d * d * i) % mod
dp1 = (dp1 * 10 + d * i) % mod
ans = (ans + dp) % mod
print(ans)f[i], dp1[i - 1] * (N[i - 1] - '0') * 20 có thể lên tới khoảng $10^9 \cdot 9 \cdot 20 \approx 1.8 \cdot 10^{11}$, vẫn vừa long long, nên lấy modulo sau khi nhân là an toàn. Bản Python mình viết thêm chỉ giữ 2 biến thay cho 2 mảng, vì f[i] chỉ phụ thuộc vào f[i − 1] và f1[i − 1].Mình đã kiểm tra code với 300 số ngẫu nhiên, so với cách cộng trực tiếp bình phương mọi số con, đều cho cùng kết quả. Với $N$ dài $10^6$ chữ số, bản C++ chạy khoảng 0.05 giây, bản Python khoảng 0.5 giây.
Nhận xét
Đăng nhận xét