题解：P9563 [SDCPC 2023] Be Careful 2

· · 题解

题意

给定 [0, N] \times [0, N] 的平面直角坐标系，其中给定 K 个点。

如果一个正方形是合法的，需要满足：

求出所有合法正方形的面积和。常规质数模数。

题解

考虑容斥。对于给定点集合 S，若钦定覆盖 S 中的点的正方形面积和为 K，则贡献为 (-1)^{|S|} \times K。“覆盖 S 中的点”也可以被表述为包含 S 的包围盒。其中，点集的包围盒指的是最小的覆盖点集内点的合法矩形。

如果包围盒 X 满足：同时有点集 S, T 的包围盒是 X，且 S \sub T，那么定义 X 是没有贡献的。也就是说，由于一个点的存在与否不影响这个包围盒，容斥系数 -1 会被奇偶抵消。因此，我们只需要计算有贡献的包围盒。

可以说明，有贡献的包围盒只有 O(K^2) 个：

假设包围盒对应的唯一点集大小为 4，其中最左的为 L，最右的为 R，那么当确定 L, R 后可以唯一确定余下的两个点。例如，最上的点 U 一定是高于 L, R 且横坐标在 (L, R) 中最低的点。

可以使用 O(K^2) 的复杂度求出所有的包围盒，接下来需要计算包围盒的贡献。设该包围盒的左上角、右下角为 (X_0, Y_0), (X_1, Y_1)，则贡献

K = \sum_{d} d^2 \times w_x(d) \times w_y(d)

其中

w_x(d) = \max(0, \min(X_0 - 1, n - d) - \max(0, X_1 - d - 1) + 1)\\ w_y(d) \space \text{is a very similar one}

因此，该式可以被表示为一个分段的、最多四次的多项式。可以直接求出端点，插值求出多项式，计算四次多项式前缀和。