题解：CF1270F Awesome Substrings

BLuemoon_ · 2025-02-18 17:10:51 · 题解

link

思路

考虑根号分治，令 B=\sqrt{n}，s_i 为长度为 i 的前缀中 1 的数量。

设当前段 [l,r] 满足条件时，d 为 r-l+1 与 s_r-s_{l-1} 的比值。

若 d\le B，将式子转化，得到：ds_r-r=ds_{l-1}-(l-1)，那么可以枚举 d，求出所有 ds_i-i，用桶存下来后算答案，这部分时间复杂度为 O(nB)。

若 d>B，那么 p=s_r-s_{l-1}<\frac{n}{B}，于是可以枚举 p 和区间左端点 l，那么可以双指针维护 r 的所有可能位置即从 l 开始 1 的数量达到 p 后的极长全 0 连续段。再直接除去 p 就可以了，但是需要保证 r-l>pB，否则就会和 d\le B 算重。这部分时间复杂度为 O(\frac{n^2}{B})。

总时间复杂度为 O(nB+\frac{n^2}{B})=O(n\sqrt{n})。

代码

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5, kMaxB = 455;

LL n, B, s[kMaxN], x, ans;
int cnt[kMaxN * kMaxB];
string t;

int main() {
  cin >> t, n = t.size(), t = ' ' + t, B = sqrt(n);
  for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + t[i] - '0';
  }
  for (LL j = 1; j <= B; j++) {
    for (int i = 0; i <= n; i++) {
      x = j * s[i] - i + n, cnt[x]++;
    }
    for (int i = 0; i <= n; i++) {
      x = j * s[i] - i + n, ans += 1ll * (cnt[x] - 1) * cnt[x] / 2, cnt[x] = 0;
    }
  }
  for (LL j = 1; j <= B; j++) {
    for (LL i = 0, L = 1, R = -1; i <= n; i++) {
      for (; L <= n && s[L] - s[i] < j; L++) {
      }
      if (L == n + 1) {
        break;
      }
      !~R && (R = L);
      for (; R < n && s[R + 1] - s[i] <= j; R++) {
      }
      LL l = max(L - i, B * j + 1), r = R - i;
      l <= r && (ans += r / j - (l - 1) / j);
    }
  }
  cout << ans << '\n';
  return 0;
}