[RMI 2024] 八边形 题解

vegetable_king · 2025-03-17 11:52:45 · 题解

可能更好的阅读体验

最构式的一集。

下面定义原题中输入的八个变量依次为 A, B, C, D, E, F, G, H。

不考虑多边形面积非零这条限制，我们相当于是在统计自然数八元组 (a, b, c, d, e, f, g, h)，满足：

最后将答案减去 \min(a, e) + \min(b, f) + \min(c, g) + \min(d, h) + 1 即可。

跳过一些推导，我们可以得到：

将其改写成下列形式：

定义 calc(A, B, x) 为满足 0 \le a \le A, 0 \le b \le B, a - b = x 的自然数对 (a, b) 个数，那么有 calc(A, B, x) = \max(\min(A, B - x) + \min(0, x) + 1, 0)。

令 f_a(x) = calc(E, A, x), f_b(x) = calc(B, F, x), f_c(x) = calc(G, C, x), f_d(x) = calc(D, H, x)，那么对于一对 X, Y，答案为 f_a(X - Y)f_b(X)f_c(X + Y)f_d(Y)，可以 O(1) 计算，那么我们枚举 X, Y 即可做到 O(N^2)。

考虑少枚举一维。calc(*) 显然是一个只有 O(1) 段的分段一次函数，对于一个确定的 Y，定义 f_Y(X) = f_a(X - Y)f_b(X)f_c(X + Y)，那么 f_Y 是一个只有 O(1) 段的分段三次函数，它的断点由 f_a, f_b, f_c 的断点平移后合并得到。考虑对每一段做个插值就能快速算出一段的 f_Y 之和。这样对于一个确定的 Y，可以 O(1) 计算 \sum_X f_Y(X)，那么我们枚举 Y 即可做到 O(N)。

继续优化。定义 f'(Y) = f_d(Y) \sum_X f_Y(X)，我们尝试用类似的方法优化之。可以感觉到，f'_Y 应该是一个只有 O(1) 段的分段五次函数 （f_Y 是三次，求和后变成四次，乘上 f_d(Y) 变成五次，如果不知道具体是几次的话试试就好了），同时它的断点应该就是 f_a, f_b, f_c 的断点的相对位置改变的所有点与 f_d 断点合并的结果，原因大概是当 f_a, f_b, f_c 的断点相对位置不变时我们可以简单刻画出 f'(Y) 的变化。具体证明应该也是可以的，但是比较麻烦。