Đếm đoạn con có tổng bằng K

Bối cảnh

Trong một chuỗi giao dịch theo thời gian, mỗi phần tử có thể dương hoặc âm. Ban phân tích quan tâm đến các khoảng thời gian liên tiếp có tổng biến động đúng bằng K. Mỗi cặp chỉ số (L,R) với L≤R tạo thành một đoạn con khác nhau, kể cả khi giá trị bên trong trùng nhau. Nhiệm vụ là đếm tổng số đoạn con có tổng bằng K.

Nếu cộng lại từng đoạn từ đầu, ba vòng lặp sẽ thực hiện nhiều phép cộng lặp lại. Tại B10, giáo trình đã chạm tới tư duy prefix sum: sau khi xây dựng tổng tích lũy, tổng của bất kỳ đoạn [L,R] có thể được lấy bằng một phép trừ. Bài Medium này chưa yêu cầu map/hashing của module sau; vì vậy vẫn duyệt mọi cặp biên nhưng tối ưu phần tính tổng đoạn.

Điểm chính là phân biệt "số phần tử bằng K" với "số đoạn liên tiếp có tổng K", và dùng prefix để tránh cộng lại nội dung đoạn.

Yêu cầu

1. Xây pre[i+1]=pre[i]+a[i].
2. Duyệt mọi L và R.
3. Tổng đoạn là pre[R+1]-pre[L]; nếu bằng K thì tăng đáp án.

Input

Dòng 1: n K. Dòng 2: n số nguyên.

Output

Một số nguyên: số đoạn con liên tiếp có tổng đúng K.

Ràng buộc

1 ≤ n ≤ 2000, |a[i]|,|K| ≤ 10^9.

Ví dụ 1

Input

5 5
1 2 3 2 5

Output

3

Giải thích

Ta cần đếm mọi đoạn con liên tiếp có tổng đúng K=5. Dùng prefix sum, tổng đoạn [L,R] được tính bằng pre[R+1]-pre[L], rồi thử mọi cặp L,R. Ba đoạn thỏa là [1,2] = 2+3, [2,3] = 3+2 và [4,4] = 5. Không có đoạn nào khác có tổng 5, nên đáp án là 3.

Ví dụ 2

Input

4 0
0 0 0 0

Output

10

Giải thích

Cả bốn phần tử đều bằng 0 và K=0, vì vậy mọi đoạn con không rỗng đều có tổng 0. Với n=4, số đoạn con là 4+3+2+1 = 10 (tương đương n(n+1)/2). Do đó chương trình đếm được 10 đoạn thỏa và in 10.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: static arrays, prefix sums, subarray enumeration, counting, long long
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100