1 条题解
-
0
为了好写,显然将询问差分成 。
考虑连续段数量的另一种刻画:。所以转而对每两列之间考虑有几行使得相邻不同。
即对 和 列之间计数有多少个 满足 。推简单二维容斥式子得到当 时答案为 $\lfloor\frac{V}{j}\rfloor+\lfloor\frac{V}{j-1}\rfloor-\lfloor\frac{V}{\text{lcm}(j,j-1)}\rfloor$。 显然为 。
考虑前一半,显然只要求 。整除分块求之。具体地,当 时枚举 ,当 时枚举 ,即可做到 复杂度。
考虑后一半,。当 时该式子值为 ,当值非零时 ,所以复杂度仍然是 。
总时间复杂度 ,常数小的离谱。
- 1
信息
- ID
- 946
- 时间
- 1000~4000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 3
- 已通过
- 2
- 上传者