The Task "Paint" – Analysis of the Solution

In the task Paint we have an array x₁…xₙ, and for each of the q types of buckets (with capacity yᵢ) we need to count how many contiguous subsequences have a sum divisible by yᵢ.

The idea (the key mathematical transformation)

Let pref[i] be the prefix sum of the first i elements (with pref[0] = 0). The sum of the segment [l+1..r] is pref[r] - pref[l]. This sum is divisible by y exactly when

(pref[r] - pref[l]) % y == 0 ⇔ pref[r] % y == pref[l] % y

So for a fixed y the number of valid segments equals the number of pairs of prefixes with the same remainder modulo y.


1) Naive (correct but slow)

Checking all pairs (l, r) directly gives a simple, clear implementation, but it is O(n²) for one value of y:

// Naive solution (pseudocode / C++)
for (int r = 1; r <= n; ++r) {
  for (int l = 0; l < r; ++l) {
    long long s = pref[r] - pref[l];
    if (s % y == 0) ans++;
  }
}

Comment: this is correct — it checks all subsequences — and for n = 8000 it may be acceptable once, but if you have to do it for each of the q types (e.g. q = 8000), the time becomes too long (O(n²·q)).

An example on a small array

Let x = [4,2,3], y = 4 — the naive approach checks all 6 segments and finds 1 (only [4]).


2) A fast and practical solution — prefix sums + a map of remainders (O(n) for one y)

We use the idea from "The idea" and count how many times each remainder pref[i] % y has appeared so far. Every time we reach the remainder r, the number of new segments ending at that point equals the number of earlier prefixes with the same remainder.

Correct C++ code

// Correct solution: O(n) for each y
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<long long> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];

    vector<int> y(q);
    for (int i = 0; i < q; ++i) cin >> y[i];

    // pref[0] = 0; pref[i] = sum of the first i elements
    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + x[i - 1];

    for (int t = 0; t < q; ++t) {
        int mod = y[t];
        unordered_map<int, long long> cnt;
        long long ans = 0;

        // important: the empty prefix (pref[0]) counts — that is why cnt[0] = 1
        cnt[0] = 1;

        for (int i = 1; i <= n; ++i) {
            int r = pref[i] % mod;
            if (r < 0) r += mod; // safety if you use negative values (rarely needed)
            ans += cnt[r];
            cnt[r]++;
        }
        cout << ans << '\n';
    }
    return 0;
}

Explanation of the code

  • We compute the prefix sums pref[0..n] (with pref[0]=0).
  • For the given mod (i.e. y[t]) we create a map cnt that remembers how many times each remainder has been seen so far.
  • We initialize cnt[0] = 1 because a segment that starts at the first element corresponds to the pair (pref[0], pref[r]).
  • For every i we add to the result the number of earlier prefixes with the same remainder, and then increase the count for that remainder.

Time and memory complexity

  • Time: O(n) for one y (so O(n·q) in total).
  • Memory: O(n) in the worst case (for the map of remainders).
  • Note: instead of unordered_map you can use vector<long long>(mod) if mod is small enough — this is often faster (no hashing).

3) Common mistakes and pitfalls (from the two solutions above)

  • Missing prefix[0] = 0 — if you do not include the empty prefix, subsequences starting at position 1 will not be counted.
  • Going out of bounds — the prefix loops must go up to i <= n with the indexing x[i-1].
  • Counting only the cases l=0 — a mistake when you check only whether pref[i] % mod == 0 (this counts only segments starting at position 1).
  • Uninitialized access — if you read or use values before they have been read in.

4) A small numerical example — step by step

For the array x = [4,2,3,6,8] and mod = 4:

ipref[i]pref[i] % 4cnt beforeadded to anscnt after
000--0cnt[0]=1
140cnt[0]=1+1cnt[0]=2
262cnt[2]=0+0cnt[2]=1
391cnt[1]=0+0cnt[1]=1
4153cnt[3]=0+0cnt[3]=1
5233cnt[3]=1+1cnt[3]=2

In total there are 2 valid segments ([4] and [8]) — this matches the example.

Input for this example and the program's output:

5 1
4 2 3 6 8
4
2

5) Additional implementation tips

  • Use long long for the prefix sums (the sum can grow up to n·10⁶).
  • Initialize the map with cnt[0]=1 before going through the prefixes.
  • If most of the yᵢ are small (< 10⁶ and memory allows it), use a vector instead of unordered_map for speed.
  • If q is very large and some y values repeat, cache the results for the same y instead of computing them again.

6) Conclusion

The most important transformation is recognizing that the sum of a segment can be expressed as a difference of prefix sums, and that the divisibility condition is equivalent to the equality of the remainders. This allows moving from O(n²) (naive) to O(n) for one y (a map or a vector of remainders) — practical and efficient for the constraints given in the task.