Đếm Đoạn Có Tổng Chia Hết · canuc80k0228

Cho dãy $A$ gồm $N$ số nguyên. Một đoạn con là một dãy phần tử liên tiếp, không rỗng, được xác định bởi hai chỉ số $l$ và $r$ ( $1 \leq l \leq r \leq N$ ).

Hãy đếm số đoạn con có tổng

A_{l} + A_{l + 1} + \dots + A_{r}

chia hết cho $N$ .

Input

Dòng đầu chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $A_{1}, A_{2}, \dots, A_{N}$ .

Output

In một số nguyên - số đoạn con thỏa điều kiện.

Constraints

$1 \leq N \leq 2 \cdot 1 0^{5}$ .
$- 1 0^{9} \leq A_{i} \leq 1 0^{9}$ .
Đáp án có thể vượt giới hạn số nguyên $32$ bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6
2 -3 4 1 -4 6

Output

Giải thích: Ba đoạn có tổng chia hết cho $6$ là $[1, 5]$ có tổng $0, [1, 6]$ có tổng $6$ và $[6, 6]$ có tổng $6$ . Không có đoạn nào khác thỏa điều kiện.

Ý tưởng: Gọi P[i] là tổng A_1..A_i, với P[0]=0. Tổng đoạn [l,r] chia hết cho N khi
Ý tưởng: P[r] ≡ P[l-1] (mod N).
Ý tưởng: Duyệt các prefix từ trái sang phải. cnt[x] lưu số prefix trước đó có phần dư x. Prefix hiện tại tạo một đoạn hợp lệ với từng prefix trước cùng phần dư, nên cộng cnt[rem] vào đáp án rồi tăng bộ đếm. Khởi tạo cnt[0]=1 cho prefix rỗng và chuẩn hóa phần dư âm về 0..N-1.
Chứng minh tính đúng: Phép biến đổi đồng dư tạo song ánh giữa mỗi đoạn hợp lệ kết thúc tại r và một prefix trước r có cùng phần dư với P[r]. Tại thời điểm xử lý r, cnt[rem] đếm đúng các prefix đó, nên số được cộng là chính xác. Mỗi đoạn có một đầu phải duy nhất, vì vậy tổng qua mọi r đếm mỗi đoạn đúng một lần và không đếm đoạn rỗng.
Độ phức tạp: Thời gian O(N), bộ nhớ O(N); đáp án dùng long long.