Hướng dẫn giải của Tổng độ dài của các phần tử
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for sumlen: Tổng độ dài của các phần tử
Hiểu bài toán
Bài toán yêu cầu tính tổng có trọng số của tất cả các subarray của mảng. Cụ thể, với mỗi subarray bắt đầu tại chỉ số L và kết thúc tại chỉ số R (1 ≤ L ≤ R ≤ N), ta tính giá trị f(L, R) * g(L, R)^3, trong đó f(L, R) là tổng các phần tử trong subarray và g(L, R) là độ dài của subarray (R - L + 1). Cần in kết quả modulo 10^9 + 7.
Ví dụ với mảng [2, 3]:
- Subarray [2]: f=2, g=1 => 2 * 1^3 = 2
- Subarray [2, 3]: f=5, g=2 => 5 * 2^3 = 40
- Subarray [3]: f=3, g=1 => 3 * 1^3 = 3 Tổng = 2 + 40 + 3 = 45.
Các cách tiếp cận
Cách Brute Force
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long total = 0;
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = i; j < n; j++) {
sum = (sum + a[j]) % MOD;
long long len = j - i + 1;
long long term = sum * len % MOD;
term = term * len % MOD;
term = term * len % MOD;
total = (total + term) % MOD;
}
}
cout << total << endl;
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Duyệt qua tất cả các subarray (O(N^2) subarray). Với mỗi subarray, tính tổng các phần tử và độ dài, sau đó nhân lại theo công thức. Cách này chỉ khả thi với N rất nhỏ (≤ 2000) nhưng quá chậm cho N=10^5.
Cách Công thức t tổng quát (Mathematical)
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INV2 = 500000004;
const long long INV6 = 166666668;
long long S1(long long n) {
if (n <= 0) return 0;
n %= MOD;
return n * (n + 1) % MOD * INV2 % MOD;
}
long long S2(long long n) {
if (n <= 0) return 0;
n %= MOD;
return n * (n + 1) % MOD * (2 * n + 1) % MOD * INV6 % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<long long> P(n + 1, 0);
for (int i = 1; i <= n; i++) {
P[i] = (P[i-1] + a[i]) % MOD;
}
long long ans = 0;
// Với mỗi đoạn [L, R], ta có:
// f(L,R) = P[R] - P[L-1]
// g(L,R) = R - L + 1
// Cần tính tổng: sum_{L=1..n} sum_{R=L..n} (P[R] - P[L-1]) * (R - L + 1)^3
// Phân tích (R - L + 1)^3 = ... và dùng các hàm tổng S1, S2
// Công thức chi tiết:
// Đặt x = L-1, y = n-R, k = R-L+1
// Với mỗi độ dài k từ 1 đến n:
// Số đoạn có độ dài k là (n - k + 1)
// Tổng f(L,R) của các đoạn độ dài k là:
// sum_{i=1..n-k+1} (P[i+k-1] - P[i-1])
// = Q[n] - Q[k-1] - Q[n-k] (với Q là tổng tiền tố của P)
long long Qn = 0;
for (int i = 1; i <= n; i++) {
Qn = (Qn + P[i]) % MOD;
}
vector<long long> Q(n + 1, 0);
for (int i = 1; i <= n; i++) {
Q[i] = (Q[i-1] + P[i]) % MOD;
}
for (int k = 1; k <= n; k++) {
long long sum_f = (Qn - Q[k-1] - Q[n-k]) % MOD;
if (sum_f < 0) sum_f += MOD;
long long term = sum_f * k % MOD;
term = term * k % MOD;
term = term * k % MOD;
ans = (ans + term) % MOD;
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Phân tích bài toán theo độ dài k của subarray. Với mỗi độ dài k, tính tổng các giá trị f(L,R) của tất cả các subarray có độ dài k, sau đó nhân với k^3. Để tính tổng f(L,R) cho đoạn độ dài k, ta dùng kỹ thuật tổng tiền tố (prefix sum). Cụ thể, tổng các subarray độ dài k là tổng của (P[i+k-1] - P[i-1]) với i chạy từ 1 đến n-k+1. Dùng mảng Q là tổng tiền tố của P để tính nhanh.
Cách Tối ưu với Biến đổi toán học
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// Tính prefix sum và tổng tiền tố của prefix sum
vector<long long> P(n + 1, 0);
vector<long long> Q(n + 1, 0);
for (int i = 1; i <= n; i++) {
P[i] = (P[i-1] + a[i]) % MOD;
Q[i] = (Q[i-1] + P[i]) % MOD;
}
long long totalQ = Q[n];
long long ans = 0;
// Duyệt theo độ dài len của subarray
for (int len = 1; len <= n; len++) {
// Tính tổng các f(L, R) có độ dài len
// sum_f = sum_{i=1}^{n-len+1} (P[i+len-1] - P[i-1])
// = (Q[n] - Q[len-1] - Q[n-len]) % MOD
long long sum_f = (totalQ - Q[len-1] - Q[n-len]) % MOD;
if (sum_f < 0) sum_f += MOD;
// len^3 % MOD
long long len3 = (long long)len * len % MOD * len % MOD;
ans = (ans + sum_f * len3) % MOD;
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là phiên bản tối ưu và trực quan nhất của Approach 2. Thay vì dùng S1, S2, ta dùng kỹ thuật tổng tiền tố để tính tổng f(L,R) cho mỗi độ dài len. Với mỗi độ dài len, có (n - len + 1) subarray. Tổng f(L,R) của chúng bằng tổng của (P[i+len-1] - P[i-1]) với i chạy từ 1 đến n-len+1. Bằng cách nhóm lại, ta thấy tổng này bằng Q[n] - Q[len-1] - Q[n-len]. Vòng lặp chạy O(n) lần, mỗi lần tính O(1).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(n) | Brute Force |
| 2 | O(n) | O(n) | Công thức t tổng quát (Mathematical) |
| 3 | O(n) | O(n) | Tối ưu với Biến đổi toán học |
Bài học kinh nghiệm
- Bài toán có thể được chia nhỏ theo độ dài của subarray. Với mỗi độ dài k, tất cả các subarray có cùng độ dài k sẽ có trọng số g(L,R)^3 = k^3 như nhau. Vì vậy, ta chỉ cần tính tổng f(L,R) của tất cả các subarray độ dài k rồi nhân với k^3.
- Sử dụng kỹ thuật tổng tiền tố (Prefix Sum) để tính nhanh tổng các phần tử trong mảng và tổng các tổng con. Cụ thể, để tính tổng f(L,R) của các subarray có độ dài k, ta cần tính tổng của (P[i+k-1] - P[i-1]) với i chạy từ 1 đến n-k+1. Bằng cách dùng một mảng Q là tổng tiền tố của P, ta rút gọn phép tính này thành Q[n] - Q[k-1] - Q[n-k].
- Công thức tổng quát cho bài toán có thể suy ra bằng cách phân tích đa thức (R-L+1)^3 và đổi thứ tự tổng hợp, nhưng cách tiếp cận chia theo độ dài k và dùng prefix sum thường dễ hiểu và dễ cài đặt hơn.
Lỗi thường gặp
- Lỗi số học modulo: Quên % MOD sau mỗi phép nhân hoặc cộng lớn, đặc biệt khi tính các bình phương hoặc lũy thừa. Ví dụ: (a * b) % MOD, không phải (a % MOD * b) % MOD nếu a, b đã được lấy modulo trước đó.
- Sai lệch chỉ số mảng: Trong C++, mảng thường bắt đầu từ 0, nhưng các công thức tổng quát thường tiện dùng 1-based indexing. Cần chú ý chuyển đổi đúng cách khi cài đặt (ví dụ: L-1, R-L+1).
- Số âm sau phép trừ modulo: Khi tính (A - B) % MOD, nếu A < B, kết quả sẽ là số âm. Cần kiểm tra và cộng MOD nếu cần (ví dụ: (A - B + MOD) % MOD).
- Tràn số (Overflow): Khi nhân các số lớn (lên tới 10^9) với nhau, kết quả có thể vượt quá 64-bit integer. Cần ép kiểu sang __int128 hoặc dùng phép nhân có modulo an toàn (modular multiplication) nếu ngôn ngữ hỗ trợ.
Bình luận