**Khai báo biến:** Gọi xâu nhị phân độ dài $n$ là $st$.
**Dùng mảng tổng tiền tố:** mảng $a$ với $a[i]$ lưu số kí tự 0 từ vị trí 0 đến i, mảng $b$ với $b[i]$ lưu số kí tự 1 từ vị trí 0 đến i
**Ý tưởng:** vì đề bài yêu cầu đếm số lượng xâu con liên tiếp có tỉ lệ giữa số 0 và số 1 là $\dfrac{x}{y}$. Ta có công thức:
$\dfrac{a[i]}{b[i]} = \dfrac{x}{y}$ $\Longleftrightarrow$ $a[i]$ $\times$ $y = b[i]$ $\times$ $x$
Khi đó, ta nhân cả mảng $a$ với $y$, mảng $b$ với $x$. Gọi mảng $c$ với $c[i]$ là hiệu $a[i] - b[i]$. Bài toán trở thành đếm số cặp $i,j$ sao cho $i<j$ và $c[i] = c[j]$
Để đếm số cặp $i,j$ thỏa mãn điều kiện trên thì ta có nhiều cách như dùng đếm phân phối và tìm kiếm nhị phân (trong code hướng dẫn thì dùng đếm phân phối).
Code C++:
```
#include <bits/stdc++.h>
const int N=1e5;
using namespace std;
string st;
int n,a[N+5],b[N+5],x,y;
unordered_map<int,int>f;
long long res=0;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>x>>y>>st;
n=st.length();
a[0]=(st[0]=='0');
b[0]=(st[0]=='1');
for(int i=1;i<n;++i){
a[i]=a[i-1]+(st[i]=='0');
b[i]=b[i-1]+(st[i]=='1');
}for(int i=0;i<n;++i){
a[i]*=y;
b[i]*=x;
}for(int i=0;i<n;++i)a[i]-=b[i];
++f[0];
for(int i=0;i<n;++i){
res+=f[a[i]];
++f[a[i]];
}cout<<res;
return 0;
}
```
hvnamyd
Created at
3 likes