题解：P12522 [Aboi Round 1] 限りなく灰色へ

WorldMachine · 2024-12-07 15:39:14 · 题解

经典结论：(x_1,y_1) 能看到 (x_2,y_2) 当且仅当 \gcd(x_1-x_2,y_1-y_2)=1。

枚举 x 坐标，那么对于点 i，要对所有满足 \gcd(x-x_i,y-y_i)=1 的 y 计算贡献。记前者为 \Delta x，问题转化为：

• 长度为 Y 的序列，维护下标与 \Delta x 互质的位置加 1，最后求整个序列。

容斥，先全部加 1，枚举 \Delta x 的每个因子 d，将所有满足 i\mid d 的位置加上 \mu(d) 即可。满足 \mu(d)\not=0 的 d 只有 2^{\omega(V)} 个，最大也只有 16，可以接受。

由于这里还有一个 y\bmod d 的位移，直接上根号分治即可。

设阈值为 B，则复杂度为 \mathcal O(XY+Xn2^{\omega(V)}\cdot\dfrac{Y}{B}+XYB)，取 B=\mathcal O(\sqrt{n2^{\omega(V)}}) 最优，复杂度为 \mathcal O(XY\sqrt{n2^{\omega(V)}})。

因为 >B 的因子很少，这个根号分治是跑不满的，X=Y=n=V=2\times10^3 的数据直接 0.5\text{s} 过。