---
# System prepended metadata

title: THT bảng B (THCS) - 2024 - 4.bbin

---

* time limit per test: **1 seconds**
* points per test: **1.0 points**
* quantity test: **20 testcase**
* memory limit per test: **1024 megabytes**
* input  : **BBIN.INP**
* output : **BBIN.OUT**
## 1. đề bài ##
**Câu 4: Xâu nhị phân cân bằng**
* Xâu nhị phân cân bằng là một xâu **khác rỗng**, chỉ gồm các chữ số ‘0’ và ‘1’ và số lượng các chữ số ‘0’ bằng số lượng các chữ số ‘1’. Ví dụ: ‘10’, ‘01’, ‘1100’, ‘1001’, ... Một xâu khác rỗng được gọi là một xâu con của một xâu **S** cho trước nếu nó là dãy ký tự liên tục trong **S**. Ví dụ: **S** = ‘101’ thì các xâu ‘1’, ‘10’, ‘01’, ‘101’ là các xâu con của **S**.
* **Yêu cầu:** Cho một xâu nhị phân **S**, đếm xem có chứa bao nhiêu xâu con nhị phân cân bằng trong xâu.
## 2. input ##
* từ tệp văn bản **BBIN.INP** gồm:
    * dòng đầu ghi số nguyên dương **n** là độ dài của xâu nhị phân **S**.
    * dòng thứ hai ghi xâu nhị phân **S**. 
## 3.output ##
* ghi vào tệp văn bản **BBIN.OUT** gồm một dòng ghi một số là số xâu nhị phân cân bằng của xâu **S**.
## 4. ví dụ ##
* **BBIN.INP**
``` 
3
101
```
* **BBIN.OUT**
```
2
```
* **BBIN.INP**
``` 
8
01101010
```
* **BBIN.OUT**
```
13
```
## 5. Subtasks ##
```
Subtasks 1 (40%): 0    <= n <= 100
Subtasks 1 (30%): 100  <= n <= 5000
Subtasks 1 (30%): 5000 <= n <= 1000000
```
## 6. dạng bài ##
* xử lí xâu
* tham
* cộng dồn
## 7. lời giải sơ lược ##
* subtasks 1, 2: duyệt kết hợp cộng dồn tìm đếm các xâu con thỏa mãn, độ phức tạp O(n^2).
* subtasks 3: sử dụng kĩ thuật duyệt tịnh tiến cập nhật {0; 1} tại mỗi vị trí, độ phức tạp O(n).
## 8. code mẫu ##
```cpp=
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) (int)v.size()
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e6)+7;

int n , a[maxN];
string s;

namespace sub1{
    bool check(){
        return n <= 1000;
    }

    void solve(){
        int ans = 0;
        for (int i = 1 ; i <= n ; i++){
            for (int j = i ; j <= n ; j++){
                if (a[j] - a[i - 1] == 0) ans++;
            }
        }
        cout << ans << "\n";
    }
}

namespace sub2{
    int cnt[2 * maxN];

    void solve(){
        ll ans = 0;
        for (int i = 1 ; i <= n ; i++){
            cnt[a[i - 1] + maxN]++;
            ans += 1ll * cnt[a[i] + maxN];
        }
        cout << ans << "\n";
    }
}

void solve(){
    cin >> n >> s;
    for (int i = 1 ; i <= n ; i++) a[i] = (s[i - 1] == '1') ? +1 : -1 , a[i] += a[i - 1];
    if (sub1::check()) return sub1::solve();
   return sub2::solve();
     
}

#define name "BBIN"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen(name".inp" , "r" , stdin);
    freopen(name".out" , "w" , stdout);
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}
```