Overview

Find the number of contiguous subsequences (intervals) of sweets whose total weight is a multiple of \(K\).

Analysis

In this problem, we need to count the number of contiguous subsequences whose sum is a multiple of \(K\).

A naive approach would be to enumerate all intervals \([l, r]\), compute the sum of each, and check whether it is a multiple of \(K\). However, this takes \(O(N^2)\) time, which clearly won’t finish within the time limit (TLE) given the constraint \(N \leq 2 \times 10^5\).

The key observation is to use prefix sums.
Using the prefix sum \(S_i = A_1 + A_2 + \cdots + A_i\), the sum of the interval \([l, r]\) can be expressed as \(S_r - S_{l-1}\).
The condition for this sum to be a multiple of \(K\) is:

\[ (S_r - S_{l-1}) \equiv 0 \pmod{K} \]

In other words:

\[ S_r \equiv S_{l-1} \pmod{K} \]

This means that by “choosing two points where the prefix sum has the same remainder modulo \(K\),” the sum of the interval between them is a multiple of \(K\).

Therefore, by computing the prefix sums from left to right and recording how many times each remainder value has appeared so far, we can determine the number of valid intervals ending at the current position.

Additionally, by initializing the count for remainder 0 to 1, we can naturally handle intervals starting from the beginning (where the prefix sum itself is a multiple of \(K\)).

Algorithm

1. Compute the remainder of the prefix sum modulo \(K\) sequentially.
2. At each step, check how many times the current remainder has appeared before, and add that count to the answer.
3. Increment the occurrence count of the current remainder.
4. Initialize the occurrence count of remainder 0 to 1 at the start (corresponding to the empty prefix).

For example, given the following input:

N=5, K=3
A = [1, 2, 3, 4, 5]

The remainders of the prefix sums are, in order: - \(1 \bmod 3 = 1\) - \((1+2) \bmod 3 = 0\) - \((1+2+3) \bmod 3 = 0\) - \((1+2+3+4) \bmod 3 = 1\) - \((1+2+3+4+5) \bmod 3 = 0\)

By managing the occurrence count for each remainder and counting combinations, we can reduce the computational complexity.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(K)\) (the number of distinct remainders is at most \(K\), but in practice it depends on the number of distinct remainders that actually appear)

*Note: Since the implementation uses defaultdict, it only uses memory proportional to the number of distinct remainders that appear.

Implementation Notes

• When computing the prefix sum remainders incrementally, initialize the count for remainder 0 to 1 (to account for intervals starting from the first element).

• Intervals must contain “at least one element,” so empty intervals are not included, but they need to be handled for computational convenience.

• Using Python’s sys.stdin.read enables fast input processing (especially important when \(N\) is large).

  Source Code

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 累積和の剰余を計算
    cumsum_mod = 0
    mod_count = defaultdict(int)
    mod_count[0] = 1  # 空の累積和に対応するもの
    
    count = 0
    for i in range(N):
        cumsum_mod = (cumsum_mod + A[i]) % K
        # 同じ剰余を持つ以前の累積和の数だけ、Kの倍数になる区間が存在する
        count += mod_count[cumsum_mod]
        mod_count[cumsum_mod] += 1
        
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.