CF1270F 题解

shiruoyu114514 · 2025-11-02 16:14:32 · 题解

给定一个 01 序列，问有多少个区间满足其长度整除其和。n \le 2 \times 10^5。

首先第一时间考虑到合法的长度/和对至多只有 n \ln n 个，于是考虑求这么多次以下问题：

问有多少个长度为 p 的区间和为 q。

发现完全做不了一点！怎么办？

考虑根号分治。对于这种整除问题一个套路就是拿除数进行根号分治。在本题中即分治和。

考虑设定阈值 B。

和 \le B 的情况是容易的：直接从每个数 l 开始，枚举往后的 t \le B 个 1，对于枚举的每一个 t，求出 r 的范围使得 [l,r] 区间和为 t。然后求出范围内有多少个 B 的倍数即可。

但是和 \ge B 的情况有点难。

当除法根号分治无法处理大除数时，需要考虑商至多只有 \frac{n}{B} 个。

考虑枚举商 k。此时有 k(s_r-s_{l-1})=r-(l-1)。化简得 ks_r-r=ks_{l-1}-(l-1)，直接开桶统计即可，值域范围是 O(\frac{n^2}{B}) 个。

但是接下来得问题是我们无法对 \ge B 部分的区间和值范围进行限定，那怎么办？注意到我们是可以限制第一部分的倍率范围的，额外要求区间长度至少为 (B+1)t 即可。

取 B= \sqrt n 即可。

时间复杂度 O(n \sqrt n)。