Hướng dẫn giải của Ma trận may mắn


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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, hohoanghai5042011, tranhaian173, LongSauMui

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ĩnh cnt.
  • 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_values và mảng used.
  • 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 target hoặ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ùng unordered_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ụ int thay cho long long cho 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

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.