**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à xy. Ta có công thức:
a[i]b[i]=xy⟺a[i]×y=b[i]×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++:
#∈clude<bitsstdc++.h>const∫N=1e5;usingnamespacestd;str∈gst;∫n,a[N+5],b[N+5],x,y;unorderedmap<∫,∫>f;longlongres=0;∫ma∈(){iosbase::syncwithstdio(false);c∈.tie(0);cout.tie(0);c∈〉x〉y〉st;n=st.≤n>h();a[0]=(st[0]==′0′);b[0]=(st[0]==′1′);for(∫i=1;i<n;++i){a[i]=a[i-1]+(st[i]==′0′);b[i]=b[i-1]+(st[i]==′1′);}for(∫i=0;i<n;++i){a[i]⋅=y;b[i]⋅=x;}for(∫i=0;i<n;++i)a[i]≡b[i];++f[0];for(∫i=0;i<n;++i){res+=f[a[i]];++f[a[i]];}cout〈res;return0;}