Hướng dẫn giải của Ma trận may mắn
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ậpTác giả: , , ,
Editorial for luckysq: Ma trận may mắn
Hiểu bài toán
Cho một mảng P gồm N số nguyên dương. Ma trận A được tạo ra sao cho A[i][j] = P[i] + P[j]. Một ma trận con vuông của A có kích thước k x k (với các chỉ số hàng và cột liên tiếp) được gọi là may mắn nếu tổng tất cả các phần tử của nó bằng X. Nhiệm vụ là đếm số lượng ma trận con may mắn.
Phân tích tổng của một ma trận con vuông: Giả sử ma trận con nằm ở vị trí bắt đầu tại hàng i và cột j, với kích thước k x k. Tổng các phần tử = (P[i] + P[j]) + (P[i] + P[j+1]) + ... + (P[i+k-1] + P[j+k-1]). Điều này có thể được t tổng hợp lại:
- Dòng i contributing: k * (P[i] + P[i+1] + ... + P[i+k-1]) = k * (Sum of P[i...i+k-1])
- Cột j contributing: k * (P[j] + P[j+1] + ... + P[j+k-1]) = k * (Sum of P[j...j+k-1]) Tổng quát: Tổng = k * (sumrow + sumcol), trong đó sumrow là tổng dãy con P độ dài k bắt đầu tại i, sumcol là tổng dãy con P độ dài k bắt đầu tại j.
Vấn đề trở thành: Tìm số cặp (i, j) sao cho k * (sumrow(i) + sumcol(j)) = X, với k là độ dài của dãy con. Vì sumrow và sumcol đều là tổng của các dãy con của P độ dài k, ta có thể gọi chúng chung là value. Ta cần tìm số cặp (value1, value2) sao cho k * (value1 + value2) = X, hoặc (value1 + value2) = X/k. Điều này có nghĩa là k phải là ước của X. Với mỗi ước k của X (1 <= k <= N), ta cần tính Target = X/k. Sau đó, ta cần đếm số cặp các dãy con độ dài k trong P có tổng bằng Target.
Các cách tiếp cận
Cách Brute Force theo ước của X
// Pseudocode approach:
// 1. Tính mảng tổng tiền tố S để lấy tổng dãy con O(1)
// 2. Liệt kê tất cả các ước k của X sao cho 1 <= k <= N
// 3. Với mỗi k:
// - Target = X / k
// - Tạo map đếm tần suất các tổng dãy con độ dài k (coi như hash map)
// - Duyệt qua tất cả các dãy con độ dài k, cập nhật map
// - Duyệt lại map, với mỗi t tổng value, nếu value <= Target, tìm số cặp có tổng = Target
// (cần count[value] * count[Target - value] nhưng phải xử lý trùng lặp)
// Cấu trúc chính:
for k in divisors of X:
if k > N: continue
target = X / k
map<long long, int> freq
for i = 1 to N - k + 1:
sum = S[i+k-1] - S[i-1]
freq[sum]++
for each (sum, count) in freq:
if sum * 2 == target:
ans += count * (count - 1) / 2
else if sum < target:
ans += count * freq[target - sum]
- Time Complexity: O(N * d(X)) hoặc O(N^2) worst case (nếu X có quá nhiều ước hoặc X quá lớn)
- Space Complexity: O(N)
Phương pháp này dựa trên quan sát rằng k (kích thước ma trận con) phải là ước của X.
- Bước 1: Tính tổng tiền tố để lấy tổng của bất kỳ dãy con nào trong O(1).
- Bước 2: Liệt kê các ước của X. Với mỗi ước k:
- Tính t tổng cần thiết cho một phần (sumrow hoặc sumcol) là Target = X / k.
- Duyệt qua tất cả các dãy con độ dài k của P, tính tổng và lưu vào map (hash table).
- Sau khi có map tần suất, ta đếm số cặp (i, j) sao cho sumrow(i) + sumcol(j) = Target.
- Độ phức tạp phụ thuộc vào số lượng ước của X và số lượng dãy con. Trong trường hợp xấu nhất (số lượng ước lớn), độ phức tạp có thể cao.
Cách Tối ưu Hash Map và Kiểm soát
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
int64 X;
if(!(cin >> N >> X)) return 0;
vector<int64> P(N+1);
for(int i=1;i<=N;i++) cin >> P[i];
// Tính tổng tiền tố
vector<int64> pref(N+1, 0);
for(int i=1;i<=N;i++) pref[i] = pref[i-1] + P[i];
// Liệt kê các ước k của X
vector<int> divisors;
for(int64 d=1; d*d<=X; ++d) {
if(X % d == 0) {
if(d <= N) divisors.push_back((int)d);
int64 d2 = X / d;
if(d2 != d && d2 <= N) divisors.push_back((int)d2);
}
}
int64 answer = 0;
for(int k : divisors) {
int64 target = X / k;
if(target <= 0) continue;
// Tối ưu: Nếu target quá lớn, ta có thể prune (ví dụ target > max_sum_possible)
// max_sum_possible = sum(P) (chỉ đúng nếu k=N), chung quy lại target không thể quá lớn.
// Tuy nhiên, dùng map vẫn an toàn.
unordered_map<int64, int> freq;
freq.reserve(N - k + 1); // Giảm thời gian rehash
// Duyệt các dãy con độ dài k
for (int i = 1; i <= N - k + 1; ++i) {
int64 sum = pref[i + k - 1] - pref[i - 1];
freq[sum]++;
}
// Đếm số cặp
for (auto const& [sum, count] : freq) {
int64 rem = target - sum;
if (rem < sum) continue; // Tránh đếm trùng, chỉ xét sum <= rem
if (rem == sum) {
answer += (int64)count * (count - 1) / 2;
} else {
if (freq.count(rem)) {
answer += (int64)count * freq[rem];
}
}
}
}
cout << answer;
return 0;
}
- Time Complexity: O(N * tau(X)) (tau(X) là số lượng ước của X)
- Space Complexity: O(N)
Đây là phiên bản chi tiết và tối ưu hơn của Approach 1.
- Logic tương tự: Duyệt qua các ước k của X.
- Với mỗi k, tính t tổng Target = X/k.
- Sử dụng
unordered_map(hash map) để đếm tần suất các tổng dãy con độ dài k. - Để tránh đếm trùng lặp (ví dụ (a, b) và (b, a)), ta chỉ xét các cặp (sum, rem) sao cho sum <= rem. Nếu sum == rem, ta dùng công thức tổ hợp để chọn 2 phần tử từ
count. - Phép chia và phép lặp chỉ được thực hiện với các ước k thực sự của X, giúp giảm đáng kể thời gian xử lý so với duyệt tất cả các độ dài k từ 1 đến N.
Cách Tối ưu với mảng tĩnh và Kiểm soát Dữ liệu
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAX_VAL = 2000005; // Đủ lớn để chứa giá trị tổng (max X ~ 10^6)
int cnt[MAX_VAL];
bool used[MAX_VAL]; // Để reset cnt nhanh chóng
vector<int> touched_values;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
int64 X;
cin >> N >> X;
vector<int64> P(N);
for(int i=0;i<N;i++) cin >> P[i];
// Tính tổng tiền tố
vector<int64> pref(N + 1, 0);
for(int i=0;i<N;i++) pref[i+1] = pref[i] + P[i];
vector<int> divisors;
for(int64 d=1; d*d<=X; ++d) {
if(X % d == 0) {
if(d <= N) divisors.push_back((int)d);
int64 d2 = X / d;
if(d2 != d && d2 <= N) divisors.push_back((int)d2);
}
}
int64 ans = 0;
for(int k : divisors) {
int64 target = X / k;
if (target >= MAX_VAL) continue; // An toàn
touched_values.clear();
// Duyệt dãy con độ dài k
for (int i = 0; i <= N - k; i++) {
int64 sum = pref[i + k] - pref[i];
if (sum < MAX_VAL) {
if (!used[sum]) {
used[sum] = true;
touched_values.push_back(sum);
}
cnt[sum]++;
}
}
// Đếm số cặp
for (int val : touched_values) {
int64 rem = target - val;
if (rem < val) continue;
if (rem < MAX_VAL && used[rem]) {
if (rem == val) {
ans += (int64)cnt[val] * (cnt[val] - 1) / 2;
} else {
ans += (int64)cnt[val] * cnt[rem];
}
}
}
// Reset mảng cnt để sử dụng cho lần lặp sau
for (int val : touched_values) {
cnt[val] = 0;
used[val] = false;
}
}
cout << ans;
return 0;
}
- Time Complexity: O(N * tau(X))
- Space Complexity: O(MAX_VAL)
Đây là biến thể hiệu quả nhất, phù hợp khi giá trị của các tổng (target) nằm trong phạm vi có thể chấp nhận được (ví dụ < 2*10^6).
- Thay vì dùng
unordered_map(vốn có chi phí overhead cao), ta dùng mảng tĩnhcnt. - Vấn đề của mảng tĩnh là phải reset sau mỗi lần lặp (vì ta chỉ dùng mảng cho mỗi độ dài k). Để reset nhanh, ta dùng vector
touched_valuesvà mảngused. - Complexity về thời gian ổn định hơn do truy cập mảng O(1) tuyệt đối và không có overhead hash.
- Lưu ý: Nếu
targethoặc các tổng dãy con quá lớn (vượt quá kích thước mảng cho phép), ta phải quay lại dùngunordered_map.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * d(X)) hoặc O(N^2) worst case (nếu X có quá nhiều ước hoặc X quá lớn) | O(N) | Brute Force theo ước của X |
| 2 | O(N * tau(X)) (tau(X) là số lượng ước của X) | O(N) | Tối ưu Hash Map và Kiểm soát |
| 3 | O(N * tau(X)) | O(MAX_VAL) | Tối ưu với mảng tĩnh và Kiểm soát Dữ liệu |
Bài học kinh nghiệm
- Tổng của ma trận con vuông k x k tại (i, j) bằng k * (Tổng dãy con P độ dài k bắt đầu tại i + Tổng dãy con P độ dài k bắt đầu tại j).
- Kích thước k của ma trận con phải là ước của X.
- Bài toán quy về: Với mỗi ước k của X, đếm số cặp dãy con độ dài k trong P có tổng bằng X/k.
- Sử dụng tổng tiền tố (prefix sum) để tính tổng dãy con trong O(1).
Lỗi thường gặp
- Không kiểm tra điều kiện k <= N khi liệt kê ước của X.
- Đếm trùng lặp các cặp (i, j) và (j, i) hoặc (i, i) khi i=j.
- Sử dụng biến số sai kích thước (ví dụ
intthay cholong longcho tổng). - Quên kiểm tra các trường hợp đặc biệt khi X chia hết cho k nhưng X/k nằm ngoài phạm vi giá trị hợp lệ (quá lớn hoặc quá nhỏ).
- Hiệu năng chậm nếu dùng map không tối ưu hoặc không reserve bộ nhớ.
Bình luận