dona10khoa_nhd
## 💡 Ý tưởng :
Ta chuyển chuỗi nhị phân thành dãy số:
- `'1'` → `+1`
- `'0'` → `-1`
Khi đó, **một đoạn con có số lượng `0` = `1`** tương đương với đoạn có **tổng các số = 0**.
---
### 📶 Dùng mảng prefix sum:
Gọi `prefix[i]` là tổng các giá trị từ đầu đến vị trí `i`. Khi đó:
> Đoạn từ `l` đến `r` có tổng bằng 0 ⇔ `prefix[r] - prefix[l - 1] = 0` ⇔ `prefix[r] = prefix[l - 1]`
Vậy ta cần đếm **số cặp chỉ số (i, j)** sao cho `prefix[i] == prefix[j]`.
---
### 🔢 Thuật toán gợi ý:
1. Khởi tạo `prefix[0] = 0`
2. Duyệt qua chuỗi `S`, tính dãy `prefix[i]`
3. Dùng `unordered_map` để đếm số lần xuất hiện của mỗi giá trị `prefix[i]`
4. Với mỗi giá trị có `cnt` lần xuất hiện → có `cnt * (cnt - 1) / 2` đoạn thỏa mãn.
---
## 🕒 Độ phức tạp
- **Thời gian:** `O(n)`
- **Không gian:** `O(n)` (dùng map và mảng prefix)
---
## 🧑💻 Code C++ tham khảo ( chỉ xem khi thật sự cần thiết )
```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
//#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
#define FOR(i, a, b, x) for (ll i = (a); i < (b); i += (x))
//***************************MAIN FUNCTION************************//
//****************************************************************//
str s;
int main()
{
getline(cin,s);
ll n = s.size(), res = 0;
vector<ll> pre(n+1,0);
FOR(i,0,n,1)
{
if(s[i] == '0') pre[i+1] = pre[i] - 1;
else pre[i+1] = pre[i] + 1;
}
unordered_map<ll ,ll> cnt;
FOR(i,1,n+1,1)
{
res += cnt[pre[i]];
cnt[pre[i-1]]++;
}
cout << res;
}
dona10khoa_nhd
Created at
2 likes