## **Ý TƯỞNG:**
Kích thước n <= 1e5, vì thế bạn không thể dùng vòng for lồng(1e5 x (1e5 - 1)) để duyệt.
Ở bài này ta sử dụng kiến thức về **prefix_sum** và **map**.
### **Thành Phần:**
**- prefix[]**: Mảng cộng dồn các phần tử từ i = 1 đến i = n.
**- map[]**: Lưu số lần xuất hiện của `prefix[i]`.
### **Giải Thích:**
Cần lưu ý như sau:
$A + B = C$ <=> $B = C - A$
Nghĩa là tổng hoặc hiệu của 2 số (A,B) chỉ có thể suy ra duy nhất 1 đáp án là C.
Do vậy lưu **prefix_sum** của mảng ban đầu, duyệt lại mảng **prefix_sum** 1 lần nữa và ***trong khi duyệt***: với mỗi vị trí `prefix[i]` đếm xem có bao nhiêu
số có giá trị là `prefix[i]-x` (`x` là số đề bài cho).
`mp[prefix[i]-x]` là số lượng số có giá trị `prefix[i]-x`,
chính những số lượng số có giá trị `prefix[i]-x` này là các đoạn con liên tiếp mà tổng của đoạn con tại vị trí `prefix[i]` = `x` *(prefix[i] - (prefix[i]-x) = x)*.
Cần lưu ý **trường hợp đặc biệt** rằng có thể `x` = 0, `prefix[i]` = 0.
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, x, ans;
int prefix[100005];
map<int, int> mp;
signed main(){
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
int temp_one; cin >> temp_one;
prefix[i] = prefix[i-1] + temp_one;
mp[prefix[i]]++;
ans += mp[prefix[i] - x];
if(prefix[i] == x && prefix[i] - x != prefix[i]) ans++; //Truong hop x = 0, prefix[i] = 0
}
cout << ans;
}
// From member of Trấn Biên Highshool
```
Temrater
Created at
2 likes