题目
给定一个01串,问有多少连续子串中1的个数大于0且可以整除其长度。
题解
问题等价于\(r-l=k(pre[r]-pre[l])\),即\(r-k\cdot pre[r]=l-k\cdot pre[l]\)。假设固定一个值\(T\),当\(k<T\)时,可以枚举\(k\)统计有多少相同数对,时间复杂度\(O(nT)\)。
由于\(pre[r]-pre[l] =\frac{r-l}{k}\le\frac{n}{T}\),也就是说当\(k\ge T\)时,合法子串内1的个数不会太多,最多只有\(\frac{n}{T}\)个。此时可以固定\(l\),枚举子串中1的个数\(m\),就能确定\(r\)的范围。又\(r-l \equiv 0 \mod m\),所以就能确定合法的\(r\)有多少(注意要取\(k\ge T\))的\(r\)。时间复杂度\(O(n\frac{n}{T})\)
总时间复杂度\(O(nT+n\frac{n}{T})\),取\(T=\sqrt{n}\),最低时间复杂度为\(O(n\sqrt{n})\)。
#include <bits/stdc++.h>
#define endl '\n'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
const double eps = 1e-5;
char s[N];
int pre[N];
int main() {
IOS;
cin >> s + 1;
int n = 0;
for(int i = 1; s[i]; i++) {
n++;
pre[i] = pre[i - 1] + (s[i] == '1');
}
ll ans = 0;
int sq = sqrt(n + 0.5) + 1;
vector<int> cnt(n * sq + n + 10);
for(int k = 1; k <= sq; k++) {
vector<int> id;
for(int i = 0; i <= n; i++) {
ll d = i - 1ll * k * pre[i];
if(d + n * sq >= cnt.size()) continue;
cnt[d + n * sq]++;
id.push_back(d + n * sq);
}
for(auto d : id) {
int num = cnt[d];
ans += 1ll * num * (num - 1) / 2;
cnt[d] = 0;
}
}
for(int k = 1; k <= sq; k++) {
int l = 1, r = 1;
for(int i = 0; i < n; i++) {
while(l <= n && pre[l] - pre[i] < k) l++;
while(r <= n && pre[r] - pre[i] <= k) r++;
ans += max(0, (r - i - 1) / k - max(l - i - 1, sq * k) / k);
}
}
cout << ans << endl;
}