专栏文章

CF1270F 题解

sshiruoyu114514
CF1270F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minewa4u
此快照首次捕获于
2025/12/02 01:17
3 个月前
此快照最后确认于
2025/12/02 01:17
3 个月前
查看原文
给定一个 0101 序列，问有多少个区间满足其长度整除其和。n≤2×105n \le 2 \times 10^5。
首先第一时间考虑到合法的长度/和对至多只有 nln⁡nn \ln n 个，于是考虑求这么多次以下问题：
问有多少个长度为 pp 的区间和为 qq。
发现完全做不了一点！怎么办？
考虑根号分治。对于这种整除问题一个套路就是拿除数进行根号分治。在本题中即分治和。
考虑设定阈值 BB。
和 ≤B\le B 的情况是容易的：直接从每个数 ll 开始，枚举往后的 t≤Bt \le B 个 11，对于枚举的每一个 tt，求出 rr 的范围使得 [l,r][l,r] 区间和为 tt。然后求出范围内有多少个 BB 的倍数即可。
但是和 ≥B\ge B 的情况有点难。
当除法根号分治无法处理大除数时，需要考虑商至多只有 nB\frac{n}{B} 个。
考虑枚举商 kk。此时有 k(sr−sl−1)=r−(l−1)k(s_r-s_{l-1})=r-(l-1)。化简得 ksr−r=ksl−1−(l−1)ks_r-r=ks_{l-1}-(l-1)，直接开桶统计即可，值域范围是 O(n2B)O(\frac{n^2}{B}) 个。
但是接下来得问题是我们无法对 ≥B\ge B 部分的区间和值范围进行限定，那怎么办？注意到我们是可以限制第一部分的倍率范围的，额外要求区间长度至少为 (B+1)t(B+1)t 即可。
取 B=nB= \sqrt n 即可。
时间复杂度 O(nn)O(n \sqrt n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...