题解 CF1270F 【Awesome Substrings】

## 题意 - 给定一个长度为 $n$ 的 $01$ 串 $s$。 - 求有多少个区间 $[l,r]$ 满足 $r - l + 1$ 是 $s_{l\dots r}$ 中 $1$ 的个数的倍数。 - $n \le 2 \times 10^5$。 ## 题解 先求出前缀和 $s_{0\dots n}$，转化为求满足 $0 \le i < j \le n$ 且 $j - i = d(s_j - s_i)$ 的 $(i,j)$ 的个数，其中 $d$ 为 $\in [1,n]$ 的正整数。 考虑给定一个限制 $T$，移项得 $s_jd - j = s_id - i$，设 $f_i(d) = s_id - i$。 对于 $1 \le d \le T$ 的情况，我们对每个 $d$ 求出 $f_{0\dots n}(d)$ 的值，然后对于每个值 $x$，若有 $k$ 个 $i$ 满足 $f_i(d) = x$，则对答案有 $\binom{k}2$ 的贡献。 这一部分实现优秀的话可达到 $\mathcal O(nT)$。 对于 $T < d \le n$ 的情况，由于 $s_j - s_i = \frac{j-i} d < \frac nT$，即有贡献的 $(a,b)$ 对应的区间中 $1$ 的个数 $k < \frac nT$。因此我们对每个 $i$ 和 $k$ 找到 $j$ 的范围 $(l,r]$，其对答案的贡献为 $\lfloor \frac {r - i}k \rfloor - \lfloor \frac {l - i}k \rfloor$ 去掉 $d \le T$ 的部分。 这一部分实现优秀的话可达到 $\mathcal O(n\frac nT)$。 因此总时间复杂度为 $\mathcal O(nT + n\frac nT)$，取 $T = \sqrt n$ 即可达到最优时间复杂度 $\mathcal O(n \sqrt n)$。 ```cpp const int N = 2e5 + 7, M = 507; int n, T, s[N], a[N*M]; char c[N]; ll ans; int main() { rds(c, n), T = sqrt(n); for (int i = 1; i <= n; i++) s[i] = s[i-1] + c[i] - '0'; for (int d = 1, x; d <= T; d++) { vi p; for (int i = 0; i <= n; i++) x = s[i] * d - i + n, ++a[x], p.pb(x); while (p.size()) x = p.back(), p.pop_back(), ans += 1ll * a[x] * (a[x] - 1) / 2, a[x] = 0; } for (int k = n / T - (T * T == n); k; k--) { int l = 0; while (l < n && s[l+1] < k) ++l; if (l == n) continue; int r = l + 1; while (r < n && s[r+1] <= k) ++r; for (int i = 0; i < n; i++) { if (s[r] - s[i] < k) { if (r == n) break; l = r; while (r < n && s[r+1] - s[i] <= k) ++r; } if ((r - i) / k > T) ans += (r - i) / k - max((l - i) / k, T); } } print(ans); return 0; } ```