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;
}