Bài 34.4. Đếm Các "Khối Liên Kết" - Độ khó: Khó

LÀM BÀI
Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M
Author:
baonguyen113
Problem type

Bài 34.4. Đếm Các "Khối Liên Kết" - Độ khó: Khó

Bạn là một nhà khoa học dữ liệu đang phân tích một chuỗi các sự kiện được đánh số. Mỗi sự kiện có một "giá trị liên kết" nguyên dương. Bạn tin rằng các sự kiện có "tính liên kết" với nhau nếu tổng giá trị liên kết của một chuỗi con các sự kiện liên tiếp chia hết cho một số nguyên \(K\) đã cho. Nhiệm vụ của bạn là đếm tổng số "khối liên kết" (các chuỗi con liên tiếp) trong toàn bộ chuỗi sự kiện.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le 10^5\)). \(K\) là số nguyên dương. Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) - giá trị liên kết của các sự kiện.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số "khối liên kết" tìm được.

Ví dụ:

Input:

5 3
1 2 3 4 5

Output:

4

Giải thích:

  • Dãy sự kiện \(A = [1, 2, 3, 4, 5]\) và \(K=3\).
  • Mảng tổng cộng dồn \(P\): \(P[0]=0, P[1]=1, P[2]=3, P[3]=6, P[4]=10, P[5]=15\).
  • Các tổng tiền tố modulo \(K\):
    • \(P[0] \% 3 = 0\)
    • \(P[1] \% 3 = 1 \% 3 = 1\)
    • \(P[2] \% 3 = 3 \% 3 = 0\)
    • \(P[3] \% 3 = 6 \% 3 = 0\)
    • \(P[4] \% 3 = 10 \% 3 = 1\)
    • \(P[5] \% 3 = 15 \% 3 = 0\)
  • Chúng ta cần tìm các cặp \((i, j)\) với \(i < j\) sao cho \(P[j] - P[i]\) chia hết cho \(K\). Điều này tương đương với \(P[j] \% K = P[i] \% K\).
  • Sử dụng một bản đồ tần suất (hash map hoặc mảng nếu \(K\) nhỏ) để lưu số lần xuất hiện của mỗi giá trị \(P[idx] \% K\).
  • Duyệt qua mảng tổng tiền tố từ \(idx=0\) đến \(N\):
    • Khi duyệt đến \(P[idx]\), ta cần tìm số lượng \(P[prev\_idx]\) (với \(prev\_idx < idx\)) sao cho \(P[prev\_idx] \% K = P[idx] \% K\). Mỗi cặp như vậy tạo thành một "khối liên kết" có tổng chia hết cho \(K\).
    • Sau đó, tăng tần suất của \(P[idx] \% K\) trong bản đồ tần suất.
  • Bắt đầu với map[0] = 1 (vì \(P[0]=0\), và tổng tiền tố từ \(P[0]\) đến \(P[idx]\) cũng được tính nếu \(P[idx]\) chia hết cho \(K\)).
  • Duyệt \(idx\) từ 1 đến \(N\):
    • \(current\_rem = P[idx] \% K\).
    • Số cặp (prev_idx, idx) mà \(P[prev\_idx] \% K = current\_rem\) là map[current_rem]. Cộng giá trị này vào tổng số "khối liên kết".
    • Tăng map[current_rem] lên 1.

Quá trình:

  • map = {0: 1} (tổng tiền tố ban đầu là 0)

  • count = 0

  • \(idx=1\), \(P[1]=1\), \(P[1]\%3 = 1\).

    • count += map[1] (map[1] = 0) -> count = 0.
    • map[1]++ -> map = {0: 1, 1: 1}.
  • \(idx=2\), \(P[2]=3\), \(P[2]\%3 = 0\).
    • count += map[0] (map[0] = 1) -> count = 1. (Chuỗi con \(A[0 \dots 1]\): \(1+2=3\), chia hết cho 3)
    • map[0]++ -> map = {0: 2, 1: 1}.
  • \(idx=3\), \(P[3]=6\), \(P[3]\%3 = 0\).
    • count += map[0] (map[0] = 2) -> count = 1 + 2 = 3. (Chuỗi con \(A[0 \dots 2]\): \(1+2+3=6\), chia hết cho 3; Chuỗi con \(A[2 \dots 2]\): \(3\), chia hết cho 3)
    • map[0]++ -> map = {0: 3, 1: 1}.
  • \(idx=4\), \(P[4]=10\), \(P[4]\%3 = 1\).
    • count += map[1] (map[1] = 1) -> count = 3 + 1 = 4. (Chuỗi con \(A[1 \dots 3]\): \(2+3+4=9\), chia hết cho 3)
    • map[1]++ -> map = {0: 3, 1: 2}.
  • \(idx=5\), \(P[5]=15\), \(P[5]\%3 = 0\).
    • count += map[0] (map[0] = 3) -> count = 4 + 3 = 7. (Chuỗi con \(A[0 \dots 4]\): \(1+2+3+4+5=15\), chia hết cho 3; Chuỗi con \(A[2 \dots 4]\): \(3+4+5=12\), chia hết cho 3; Chuỗi con \(A[4 \dots 4]\): \(5\) không phải, cái này cần xét kĩ hơn)

Sửa lại giải thích:

Các chuỗi con có tổng chia hết cho 3:

  • \(A[0 \dots 1]\): \([1, 2]\), tổng 3. (\(P[2]-P[0]\))
  • \(A[0 \dots 2]\): \([1, 2, 3]\), tổng 6. (\(P[3]-P[0]\))
  • \(A[1 \dots 3]\): \([2, 3, 4]\), tổng 9. (\(P[4]-P[1]\))
  • \(A[2 \dots 2]\): \([3]\), tổng 3. (\(P[3]-P[2]\))
  • \(A[3 \dots 5]\): \([4, 5]\), tổng 9.
  • \(A[4 \dots 4]\): \([5]\) - không.
  • \(A[2 \dots 4]\): \([3, 4, 5]\), tổng 12. (\(P[5]-P[2]\))
  • \(A[0 \dots 4]\): \([1, 2, 3, 4, 5]\), tổng 15. (\(P[5]-P[0]\))

Đây là 7 chuỗi con. Vậy ví dụ đầu ra là 4 thì có thể là có điều kiện gì đó khác, hoặc chỉ xét các chuỗi con mà \(A_i\) là dương, hoặc tôi đang nhầm lẫn.

Với ví dụ \(A = [1, 2, 3, 4, 5]\) và \(K=3\): Các mảng con liên tiếp có tổng chia hết cho 3:

  1. \([1, 2]\) (tổng 3)
  2. \([3]\) (tổng 3)
  3. \([2, 3, 4]\) (tổng 9)
  4. \([3, 4, 5]\) (tổng 12)
  5. \([1, 2, 3]\) (tổng 6)
  6. \([4, 5]\) (tổng 9)
  7. \([1, 2, 3, 4, 5]\) (tổng 15) Tổng cộng có 7 chuỗi con. Nếu output là 4, có thể có ràng buộc nào đó chưa được nêu rõ, hoặc ví dụ hơi lạ. Để phù hợp với output 4, các chuỗi con phải là: \([1,2]\) \([3]\) \([2,3,4]\) \([4,5]\) Đây là 4 chuỗi. Điều gì đặc biệt về chúng? Ah, đây là một ví dụ phổ biến cho bài toán này, thường có output là 4. Trong trường hợp này, các chuỗi con là:
  • \(A[0 \dots 1]\) (tổng 3)
  • \(A[2 \dots 2]\) (tổng 3)
  • \(A[1 \dots 3]\) (tổng 9)
  • \(A[3 \dots 4]\) (tổng 9) Đúng là 4 chuỗi.

Giải thích lại với cách dùng map/frequency array:

  • Mảng tổng tiền tố \(P = [0, 1, 3, 6, 10, 15]\).

  • Các giá trị \(P[i] \% K\):

    • \(P[0]\%3 = 0\)
    • \(P[1]\%3 = 1\)
    • \(P[2]\%3 = 0\)
    • \(P[3]\%3 = 0\)
    • \(P[4]\%3 = 1\)
    • \(P[5]\%3 = 0\)

  • Khởi tạo freq_map = {0: 1} (đại diện cho \(P[0]\)), count = 0.

  • Duyệt \(idx\) từ \(1\) đến \(N\):
    • \(current\_prefix\_mod = P[idx] \% K\).
    • count += freq_map[current_prefix_mod] (số lần xuất hiện của cùng một giá trị modulo trước đó)
    • freq_map[current_prefix_mod]++

Quá trình:

  1. \(idx=0\): \(P[0]=0\). freq_map = {0: 1}, count = 0. (Đây là điểm bắt đầu)
  2. \(idx=1\): \(P[1]=1\). \(P[1]\%3 = 1\).
    • count += freq_map[1] (map[1] = 0). count = 0.
    • freq_map[1]++ -> freq_map = {0: 1, 1: 1}.
  3. \(idx=2\): \(P[2]=3\). \(P[2]\%3 = 0\).
    • count += freq_map[0] (map[0] = 1). count = 1. (Chuỗi con \(A[0 \dots 1]\) có tổng 3)
    • freq_map[0]++ -> freq_map = {0: 2, 1: 1}.
  4. \(idx=3\): \(P[3]=6\). \(P[3]\%3 = 0\).
    • count += freq_map[0] (map[0] = 2). count = 1 + 2 = 3. (Chuỗi con \(A[0 \dots 2]\) có tổng 6; chuỗi con \(A[2 \dots 2]\) có tổng 3)
    • freq_map[0]++ -> freq_map = {0: 3, 1: 1}.
  5. \(idx=4\): \(P[4]=10\). \(P[4]\%3 = 1\).
    • count += freq_map[1] (map[1] = 1). count = 3 + 1 = 4. (Chuỗi con \(A[1 \dots 3]\) có tổng 9)
    • freq_map[1]++ -> freq_map = {0: 3, 1: 2}.
  6. \(idx=5\): \(P[5]=15\). \(P[5]\%3 = 0\).
    • count += freq_map[0] (map[0] = 3). count = 4 + 3 = 7. (Chuỗi con \(A[0 \dots 4]\) có tổng 15; chuỗi con \(A[2 \dots 4]\) có tổng 12; chuỗi con \(A[4 \dots 4]\) có tổng 5 -> \(P[5]-P[4]\)).

It seems my manual count of 7 is correct with this logic, and the sample output 4 is a common "typo" or specific problem variation from a different source. I'll stick with the correct 7 based on the standard prefix sum modulo K approach. If the problem meant something else, it would need to be specified more clearly. The 4 contiguous subarrays are: [1, 2] sum=3 [3] sum=3 [2, 3, 4] sum=9 [4, 5] sum=9 Okay, the sample output 4 is tricky. It implies disjoint or maximum-length non-overlapping, or something unique. But the problem states "count all contiguous subarrays". The standard definition gives 7.

Let's assume the example output is 4 and derive a possible scenario to explain it. Perhaps, "khối liên kết" means a contiguous block that starts a new chain of divisibility, not just any subarray. This is not a standard prefix sum application interpretation.

I will use an example input/output that yields 7, or simply explain how the standard logic (which leads to 7) works. For the example of \([1, 2, 3, 4, 5]\) and \(K=3\), a standard problem would yield 7. I will change the output example to reflect the 7.

Final check on explanation with output 7:

  • P = [0, 1, 3, 6, 10, 15]
  • P_mod_3 = [0, 1, 0, 0, 1, 0]

freq_map = {0: 1} (for P[0]) total_count = 0

  • i=1: \(P[1]\%3 = 1\). total_count += freq_map[1] (0). total_count = 0. freq_map[1]++ -> freq_map = {0: 1, 1: 1}
  • i=2: \(P[2]\%3 = 0\). total_count += freq_map[0] (1). total_count = 1. freq_map[0]++ -> freq_map = {0: 2, 1: 1}
  • i=3: \(P[3]\%3 = 0\). total_count += freq_map[0] (2). total_count = 1 + 2 = 3. freq_map[0]++ -> freq_map = {0: 3, 1: 1}
  • i=4: \(P[4]\%3 = 1\). total_count += freq_map[1] (1). total_count = 3 + 1 = 4. freq_map[1]++ -> freq_map = {0: 3, 1: 2}
  • i=5: \(P[5]\%3 = 0\). total_count += freq_map[0] (3). total_count = 4 + 3 = 7. freq_map[0]++ -> freq_map = {0: 4, 1: 2}

Result: 7. This is the correct standard answer. I'll modify the example output to 7.

Ví dụ:

Input:

5 3
1 2 3 4 5

Output:

7

Giải thích:

  • Dãy sự kiện \(A = [1, 2, 3, 4, 5]\) và \(K=3\).
  • Mảng tổng cộng dồn \(P\): \(P[0]=0, P[1]=1, P[2]=3, P[3]=6, P[4]=10, P[5]=15\).
  • Chúng ta cần tìm số lượng các cặp chỉ số \((i, j)\) với \(0 \le i < j \le N\) sao cho tổng của dãy con từ \(A[i]\) đến \(A[j-1]\) (hoặc \(A[i+1]\) đến \(A[j]\) nếu 1-indexed) chia hết cho \(K\).
  • Tổng của dãy con từ \(A[i]\) đến \(A[j-1]\) là \(P[j] - P[i]\). Điều kiện chia hết cho \(K\) tức là \((P[j] - P[i]) \% K = 0\), hay \(P[j] \% K = P[i] \% K\).
  • Ta có thể giải bài toán này bằng cách duyệt qua các giá trị \(P[j]\) và đếm số lần xuất hiện của \(P[j] \% K\) ở các vị trí trước đó.
  • Sử dụng một bản đồ tần suất (std::map hoặc mảng std::vector nếu \(K\) không quá lớn) để lưu trữ số lần xuất hiện của mỗi giá trị modulo \(K\).
  • Khởi tạo freq_map[0] = 1 (vì \(P[0]=0\), đại diện cho tổng tiền tố rỗng).
  • Duyệt qua \(P[j]\) từ \(j=1\) đến \(N\):
    • Tính remainder = P[j] % K.
    • Cộng freq_map[remainder] vào tổng số "khối liên kết" (vì mỗi lần xuất hiện của remainder trước đó tạo thành một dãy con có tổng chia hết cho \(K\)).
    • Tăng freq_map[remainder] lên 1.

Các "khối liên kết" (dãy con liên tiếp có tổng chia hết cho 3) là:

  1. \([1, 2]\) (tổng 3)
  2. \([3]\) (tổng 3)
  3. \([1, 2, 3]\) (tổng 6)
  4. \([2, 3, 4]\) (tổng 9)
  5. \([4, 5]\) (tổng 9)
  6. \([3, 4, 5]\) (tổng 12)
  7. \([1, 2, 3, 4, 5]\) (tổng 15) Tổng cộng có 7 "khối liên kết".

Comments

There are no comments at the moment.

Zalo