Ma Trận May Mắn (LUCKYSQ) (Beginner Free Contest 23)

Nguồn: VNOJ – Beginner Free Contest 23 Độ khó: Khá Mảng cộng dồn Mảng đánh dấu Ước số Nhận xét

Đề bài

LUCKYSQ (Beginner Free Contest 23)

Cho một số nguyên dương $X$ và một ma trận $A$ kích thước $N \times N$. Một ma trận vuông con của $A$ được gọi là may mắn nếu giá trị của nó đúng bằng $X$, với:

• Ma trận vuông con là ma trận con của $A$ mà hai chiều kích thước của ma trận đó bằng nhau.
• Giá trị của một ma trận bằng tổng giá trị của tất cả các phần tử của ma trận đó.

Cho dãy số nguyên dương $P$ gồm $N$ phần tử, ma trận $A$ được xây dựng từ dãy $P$ theo công thức $A_{i,j} = P_i + P_j$ $(1 \le i, j \le N)$. Bạn hãy đếm số lượng ma trận vuông con may mắn của ma trận $A$.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương $N$ và $X$.
• Dòng tiếp theo chứa $N$ số nguyên dương, số thứ $i$ là phần tử $P_i$.

Kết quả: Đưa ra số nguyên duy nhất là kết quả bài toán.

Giới hạn:

• $1 \le N, X \le 10^6$.
• $1 \le P_i \le 10^6$.

Chấm điểm:

• Subtask 1 (30% số test): $1 \le N \le 50$.
• Subtask 2 (40% số test): $50 \lt N \le 1000$.
• Subtask 3 (30% số test): Không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây · Bộ nhớ: 256 MB (theo trang đề trên VNOJ).

Ví dụ 1 – input

4 90
5 5 5 5

Ví dụ 1 – output

4

Ví dụ 2 – input

5 6
1 2 3 4 5

Ví dụ 2 – output

5

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 viết lại thành bài giải chi tiết, đi đúng theo từng bước gợi ý mà mình đã trao đổi với em ấy, để các bạn thấy cách tư duy từ chỗ "bí quá" cho tới lúc AC. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Gợi ý ngắn gọn mình đưa cho em học viên ngay từ đầu: Mảng đánh dấu + Mảng cộng dồn + 1 chút tư duy logic. Các bạn thử tự làm trước rồi hẵng đọc tiếp nhé 😉.

Giải thích ví dụ cho bạn nào chưa hiểu đề:

• Ví dụ 1: $P = (5, 5, 5, 5)$ nên mọi ô $A_{i,j} = 5 + 5 = 10$. Ma trận vuông con $k \times k$ có tổng $10k^2$; muốn bằng $90$ thì $k^2 = 9$, $k = 3$. Trong ma trận $4 \times 4$ có $2 \cdot 2 = 4$ vị trí đặt hình vuông $3 \times 3$ ⇒ đáp án $4$.
• Ví dụ 2: $P = (1, 2, 3, 4, 5)$ nên $A_{i,j} = i + j$. Ma trận $1 \times 1$ có giá trị $6$ là các ô $(1,5), (2,4), (3,3), (4,2), (5,1)$ – đủ 5 ô. Ma trận $2 \times 2$ nhỏ nhất đã có tổng $2 + 3 + 3 + 4 = 12 \gt 6$, nên không còn ma trận nào khác ⇒ đáp án $5$. Để ý là ô $(1,5)$ và ô $(5,1)$ được tính là 2 ma trận khác nhau nhé.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Công thức + duyệt mọi k, i, j · O(N³) · 70%Cách 2Chỉ xét ước của X + mảng đánh dấu · 100%

Cách 1Không cần tạo ma trận, chỉ cần công thức – O(N³)

Lúc đầu em học viên làm theo kiểu: tạo ra cả ma trận $N \times N$, rồi xét ma trận $N \times N$, nếu tổng lớn hơn thì xét tiếp 4 ma trận $(N-1) \times (N-1)$ bên trong nó... Mình nhìn là thấy em xài bộ nhớ rất nhiều rồi. Với $N = 10^6$ thì ma trận có tới $10^{12}$ ô, không đời nào chứa nổi.

Điểm mấu chốt đầu tiên: không cần phải đi tạo ra cái ma trận, mà chỉ dựa theo danh sách $N$ số ban đầu là tính được tổng của mọi ma trận vuông con. Các bạn thử với $N = 4$ nhé, liệt kê ra:

$A_{11} = P_1 + P_1,\quad A_{12} = P_1 + P_2,\quad A_{13} = P_1 + P_3,\quad A_{14} = P_1 + P_4,\quad A_{21} = P_2 + P_1,\ \dots$

Giờ lấy ma trận con $2 \times 2$ gồm các hàng $1, 2$ và các cột $3, 4$:

$(P_1 + P_3) + (P_1 + P_4) + (P_2 + P_3) + (P_2 + P_4) = 2(P_1 + P_2) + 2(P_3 + P_4)$

Mỗi $P$ của hàng xuất hiện đúng $k$ lần (một lần cho mỗi cột), mỗi $P$ của cột cũng xuất hiện đúng $k$ lần (một lần cho mỗi hàng). Tổng quát lên:

Công thức tổng của ma trận vuông con

Ma trận vuông con kích thước $k \times k$, các hàng từ $i$ đến $i + k - 1$, các cột từ $j$ đến $j + k - 1$ có tổng:
$\text{Tổng} = k \cdot \big(S(i) + S(j)\big)$
trong đó $S(i) = P_i + P_{i+1} + \dots + P_{i+k-1}$ là tổng đoạn dài $k$ bắt đầu từ $i$. Dùng mảng cộng dồn $a[i] = P_1 + \dots + P_i$ thì $S(i) = a[i + k - 1] - a[i - 1]$, tính trong $O(1)$.
Viết ra code chính là: k*(pre[i+k-1]-pre[i-1]+pre[j+k-1]-pre[j-1]).

Có công thức rồi thì cách đơn giản nhất: duyệt mọi kích thước $k$ từ $1$ tới $N$, mọi hàng bắt đầu $i$, mọi cột bắt đầu $j$, tính công thức, bằng $X$ thì đếm.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

long long a[1005];   // a[i] = P1 + P2 + ... + Pi

int main() {
    int n;
    long long x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    long long res = 0;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i + k - 1 <= n; i++)
            for (int j = 1; j + k - 1 <= n; j++)
                if (k * (a[i + k - 1] - a[i - 1] + a[j + k - 1] - a[j - 1]) == x)
                    res++;
    cout << res;
    return 0;
}

n, x = map(int, input().split())
p = list(map(int, input().split()))
a = [0] * (n + 1)          # a[i] = P1 + P2 + ... + Pi
for i in range(1, n + 1):
    a[i] = a[i - 1] + p[i - 1]
res = 0
for k in range(1, n + 1):
    for i in range(1, n - k + 2):
        for j in range(1, n - k + 2):
            if k * (a[i + k - 1] - a[i - 1] + a[j + k - 1] - a[j - 1]) == x:
                res += 1
print(res)

C++▶ Chạy tay từng dòng codeCách 1: mảng cộng dồn + duyệt mọi k, i, j, kiểm tra k·(S(i) + S(j)) == x.

Dữ liệu vào (stdin) – sửa thoải mái4 90 5 5 5 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long a[1005]; // a[i] = P1 + P2 + ... + Pi

5

6int main() {

7 int n;

8 long long x;

9 cin >> n >> x;

10 for (int i = 1; i <= n; i++) {

11 cin >> a[i];

12 a[i] += a[i - 1];

13 }

14 long long res = 0;

15 for (int k = 1; k <= n; k++)

16 for (int i = 1; i + k - 1 <= n; i++)

17 for (int j = 1; j + k - 1 <= n; j++)

18 if (k * (a[i + k - 1] - a[i - 1] + a[j + k - 1] - a[j - 1]) == x)

19 res++;

20 cout << res;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ một mảng cộng dồn $N + 1$ phần tử ⇒ $O(N)$. Đã đỡ hơn rất nhiều so với việc tạo cả ma trận.
• Thời gian: 3 vòng lặp lồng nhau $k, i, j$, tổng số lần kiểm tra là $\sum_{k=1}^{N} (N - k + 1)^2 \approx \dfrac{N^3}{3}$ ⇒ $O(N^3)$. Với $N = 1000$ là khoảng $3.3 \cdot 10^8$ phép kiểm tra, mình đo trên máy chạy khoảng 0.8 giây, sát nút giới hạn 1 giây; còn $N = 10^6$ thì chịu.

Không gian$O(N)$

Thời gian$O(N^3)$

Chỉ được khoảng 70% điểm

Em học viên làm tới đây (thêm cả việc chỉ xét các ước của $X$ ở cách 2, nhưng vẫn 2 vòng lặp $i, j$ lồng nhau) thì được 14/20 test – đúng subtask 1 và 2. Subtask 3 với $N$ tới $10^6$ thì bắt buộc phải tối ưu tiếp. Bản Python của cách này còn chậm hơn nhiều, chỉ nên dùng cho $N$ nhỏ (subtask 1).

Cách 2Chỉ xét kích thước là ước của X + 2 vòng lặp rời nhau với mảng đánh dấu

Mình hỏi em học viên: đừng nói với anh là em phải đi tìm toàn bộ các ma trận con có thể nhé? Ví dụ $N = 4$, em liệt kê và tính tổng các ma trận con $1 \times 1$, $2 \times 2$, $3 \times 3$, $4 \times 4$? Ta có cách để chỉ xét một số kích thước nhất định chứ không cần phải xét toàn bộ. Hãy nhìn lại công thức, nhưng lần này đưa luôn cái "$= X$" vào:

$k \cdot \big(S(i) + S(j)\big) = X$

Nhận xét 1: k phải là ước của X

Vế trái là $k$ nhân với một số nguyên, nên muốn bằng $X$ thì $k$ bắt buộc là ước của $X$. Ban đầu em học viên không nhìn ra là tại vì em không đưa "$= X$" vào phương trình :))). Với $X \le 10^6$ thì $X$ có tối đa $240$ ước, ít hơn rất nhiều so với $N$ kích thước. Tìm các ước thì duyệt $k$ từ $1$ tới $\sqrt{X}$ là đủ: mỗi lần $k$ chia hết $X$ ta có luôn cặp ước $k$ và $X / k$.

Và khi đã cố định $k$ thì ta chỉ cần đếm số cặp $(i, j)$ sao cho:

Bài toán con với mỗi ước k

Đếm số cặp $(i, j)$ (có thứ tự, $i$ và $j$ được phép trùng nhau) với $1 \le i, j \le N - k + 1$ thỏa
$S(i) + S(j) = f, \qquad f = \dfrac{X}{k}$

Nhận xét 2: không cần 2 vòng lặp lồng nhau

Nếu vẫn duyệt for i lồng for j để kiểm tra thì mỗi ước tốn $O(N^2)$, vẫn chết với $N = 10^6$. Mình lấy một ví dụ nhỏ cho em học viên: giả sử $k = 3$ và $N = 10$, $i$ chạy từ $1$ tới $8$, mỗi $i$ ứng với một đoạn dài 3: $(1, 2, 3)$, $(2, 3, 4)$, ..., $(8, 9, 10)$. Với mọi giá trị $i$ đó thì $j$ cũng chỉ là một trong đúng các đoạn $(1, 2, 3)$, $(2, 3, 4)$... ấy thôi. Nghĩa là các tổng $S(j)$ cũng chính là các tổng $S(i)$ – chỉ có $N - k + 1$ giá trị.

Vậy làm 2 vòng lặp rời nhau là đủ:

1. Vòng 1: với mỗi $i$, đánh dấu cnt[S(i)]++ – đếm xem có bao nhiêu đoạn dài $k$ có tổng bằng từng giá trị.
2. Vòng 2: với mỗi $j$, đoạn hàng cần có tổng đúng bằng $f - S(j)$, số cách chọn chính là cnt[f - S(j)], cộng vào kết quả.

Lưu ý $X$ tối đa chỉ $10^6$, chưa kể sau khi chia cho ước số thì $f = X / k$ còn nhỏ nữa, nên mảng đánh dấu chỉ cần tới chỉ số $f \le 10^6$. Tổng nào $\ge f$ thì chắc chắn không ghép được (vì tổng kia $\ge 1$), bỏ qua luôn khỏi cần đánh dấu.

Nhận xét 3: cú chót – nếu X là số nguyên tố thì sao?

Làm tới đây em học viên vẫn bị TLE 15/20. Mình hỏi tiếp: thử nghĩ xem, nếu $X$ là số nguyên tố thì sao? Thì $k = 1$ hoặc $k = X$. Có cần phải xét $k = X$ không? Không! Vì ma trận $X \times X$ có tới $X^2$ ô, mỗi ô $\ge 2$, tổng phải $\ge 2X^2 \gt X$. Chính cái gợi ý số nguyên tố này làm em ấy nảy ra ý tưởng và AC 😁.

Tổng quát hoá lên: gọi $Min$, $Max$ là phần tử nhỏ nhất, lớn nhất của $P$. Mỗi đoạn dài $k$ có $k \cdot Min \le S(i) \le k \cdot Max$, nên:

Cắt tỉa: bỏ qua ngay các ước không thể

$2k \cdot Min \le S(i) + S(j) \le 2k \cdot Max$
Nếu $f = X / k$ nằm ngoài đoạn $[2k \cdot Min,\ 2k \cdot Max]$ thì return 0 luôn, khỏi phải duyệt mảng. Đặc biệt vì $Min \ge 1$ nên phải có $X / k \ge 2k$, tức là $k \le \sqrt{X / 2} \approx 707$ – các ước lớn (kể cả $k = X$ khi $X$ nguyên tố) đều bị loại ngay.

Minh hoạ

Em nhập $X$ và dãy $P$ (tối đa 8 số) rồi bấm Tiếp. Ma trận $A$ chỉ vẽ ra cho dễ hình dung thôi nhé, code không hề tạo nó. Ở bước đánh dấu, dải hàng tím là đoạn $i$ đang xét; ở bước đếm, cột vàng là đoạn $j$ và các ô xanh là những ma trận vuông con may mắn vừa đếm được.

X P

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int n, x;
long long a[1000005];     // a[i] = P1 + P2 + ... + Pi
long long cnt[1000005];   // cnt[v] = số đoạn dài k có tổng bằng v
long long Min = 1e18, Max = 0;

long long GetNum(int k) {
    long long f = x / k;  // cần S(i) + S(j) = f
    if (f < 2 * k * Min || f > 2 * k * Max) return 0;
    fill(cnt, cnt + f + 1, 0);
    for (int i = 1; i + k - 1 <= n; i++) {
        long long s = a[i + k - 1] - a[i - 1];
        if (s < f) cnt[s]++;
    }
    long long res = 0;
    for (int j = 1; j + k - 1 <= n; j++) {
        long long s = a[j + k - 1] - a[j - 1];
        if (s < f) res += cnt[f - s];
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        long long p; cin >> p;
        Min = min(Min, p); Max = max(Max, p);
        a[i] = a[i - 1] + p;
    }
    long long res = 0;
    for (int k = 1; k * k <= x; k++)
        if (x % k == 0) {
            if (k <= n) res += GetNum(k);
            if (x / k != k && x / k <= n) res += GetNum(x / k);
        }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, x = int(data[0]), int(data[1])
    p = list(map(int, data[2:2 + n]))
    Min, Max = min(p), max(p)
    a = [0] * (n + 1)              # a[i] = P1 + P2 + ... + Pi
    for i in range(1, n + 1):
        a[i] = a[i - 1] + p[i - 1]

    def GetNum(k):
        f = x // k                 # cần S(i) + S(j) = f
        if f < 2 * k * Min or f > 2 * k * Max:
            return 0
        cnt = [0] * (f + 1)        # cnt[v] = số đoạn dài k có tổng bằng v
        sums = [a[i + k] - a[i] for i in range(n - k + 1)]
        for s in sums:
            if s < f:
                cnt[s] += 1
        res = 0
        for s in sums:
            if s < f:
                res += cnt[f - s]
        return res

    res = 0
    k = 1
    while k * k <= x:
        if x % k == 0:
            if k <= n:
                res += GetNum(k)
            if x // k != k and x // k <= n:
                res += GetNum(x // k)
        k += 1
    print(res)

main()

Giải thích một số chỗ trong code:

1. Lúc đọc dữ liệu, mình tính luôn mảng cộng dồn a và ghi nhận Min, Max của dãy $P$ để dùng cho bước cắt tỉa.
2. Vòng for (k = 1; k * k <= x; k++) tìm các ước theo cặp $k$ và $x / k$; điều kiện x / k != k để khỏi tính 2 lần khi $x$ là số chính phương; điều kiện <= n vì ma trận vuông con không thể lớn hơn $N$.
3. Hàm GetNum(k) trả về số cặp $(i, j)$ với $S(i) + S(j) = f$. Đầu hàm xoá mảng đánh dấu từ cnt[0] tới cnt[f] (chỉ đúng phần sẽ dùng) để lần gọi trước không ảnh hưởng.
4. Điều kiện s < f vừa loại các đoạn không thể ghép (đoạn kia có tổng $\ge 1$), vừa đảm bảo chỉ số cnt[s] và cnt[f - s] luôn nằm trong mảng.

Coi chừng tràn số

Tổng một đoạn $S(i)$ có thể tới $10^6 \cdot 10^6 = 10^{12}$, và đáp án cũng có thể tới cỡ $10^{12}$ (ví dụ $P$ toàn số $1$, rất nhiều cặp đoạn thỏa) ⇒ phải dùng long long. Code mình gửi em học viên hồi đó dùng biến int cho tổng đoạn và mảng khai báo động trong hàm (long long b[f + 1] – chỉ GCC mới cho phép); ở đây mình viết lại cho chuẩn: mảng toàn cục và long long hết.

C++▶ Chạy tay từng dòng codeCách 2: chỉ xét ước k của x, cắt tỉa bằng Min/Max, đánh dấu cnt[S(i)] rồi cộng cnt[f − S(j)].

Dữ liệu vào (stdin) – sửa thoải mái4 90 5 5 5 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int n, x;

5long long a[1000005]; // a[i] = P1 + P2 + ... + Pi

6long long cnt[1000005]; // cnt[v] = số đoạn dài k có tổng bằng v

7long long Min = 1e18, Max = 0;

8

9long long GetNum(int k) {

10 long long f = x / k; // cần S(i) + S(j) = f

11 if (f < 2 * k * Min || f > 2 * k * Max) return 0;

12 fill(cnt, cnt + f + 1, 0);

13 for (int i = 1; i + k - 1 <= n; i++) {

14 long long s = a[i + k - 1] - a[i - 1];

15 if (s < f) cnt[s]++;

16 }

17 long long res = 0;

18 for (int j = 1; j + k - 1 <= n; j++) {

19 long long s = a[j + k - 1] - a[j - 1];

20 if (s < f) res += cnt[f - s];

21 }

22 return res;

23}

24

25int main() {

26 ios_base::sync_with_stdio(false); cin.tie(NULL);

27 cin >> n >> x;

28 for (int i = 1; i <= n; i++) {

29 long long p; cin >> p;

30 Min = min(Min, p); Max = max(Max, p);

31 a[i] = a[i - 1] + p;

32 }

33 long long res = 0;

34 for (int k = 1; k * k <= x; k++)

35 if (x % k == 0) {

36 if (k <= n) res += GetNum(k);

37 if (x / k != k && x / k <= n) res += GetNum(x / k);

38 }

39 cout << res;

40 return 0;

41}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng cộng dồn $N + 1$ phần tử và mảng đánh dấu tới chỉ số $X$ ⇒ $O(N + X)$.
• Thời gian: tìm ước mất $O(\sqrt{X})$. Mỗi ước $k$ qua được bước cắt tỉa thì tốn $O(N + f)$ cho 2 vòng lặp rời nhau và việc xoá mảng đánh dấu. $X \le 10^6$ có tối đa $240$ ước, mà nhờ cắt tỉa chỉ những ước $k \le \sqrt{X/2}$ mới phải duyệt, nên thực tế chỉ khoảng vài chục tới hơn trăm lần duyệt mảng ⇒ $O(d(X) \cdot N)$ với $d(X)$ là số ước của $X$.

Không gian$O(N + X)$

Thời gian$O(\sqrt{X} + d(X) \cdot N)$

Về bản Python

Với C++, trường hợp nặng nhất mình thử ($N = 10^6$, $X = 720720$ – số có tới 240 ước, $P$ ngẫu nhiên) chạy khoảng 0.4 giây. Bản Python cùng thuật toán thì phải mất cỡ 18 giây trên cùng máy, nên Python chỉ an toàn ở 2 subtask đầu; muốn ăn trọn subtask 3 thì các bạn dùng C++ nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên nhỏ ($N \le 8$), so với code vét cạn tạo hẳn ma trận $A$ rồi cộng từng ma trận vuông con – khớp hết. Test lớn: cách 2 (C++) với $N = 10^6$ chạy 0.1–0.4 giây; cách 1 (C++) với $N = 1000$ chạy khoảng 0.8 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇