题解：P10760 [BalticOI 2024] Portal

· · 题解

[BalticOI 2024] Portal

先考虑一维的怎么做。稍微思考一下就可以发现由于以每个点作为坐标轴原点时的染色要相同，所以染色方案一定是将一个颜色序列作为循环节循环，循环节长度必须是所有相邻两个位置的差的因数，所以直接取最大公因数。时间复杂度是 \operatorname{O}(n\log V)。

考虑拓展到二维。由于题目中对合法方案的 check 相当于是将平面直角坐标系的原点平移后与原坐标系完全重合，所以可以直接先选择一个点作为原点。即设点序列为 (x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)，那么可以选择一个 p 使得 1\le p\le n，获得一个新序列 (x_1-x_p,y_1-y_p),(x_2-x_p,y_2-y_p),\cdots,(x_n-x_p,y_n-y_p)。下文中令 a_i=x_i-x_1,b_i=y_i-y_1，即将坐标轴原点平移至 1 号点处。

结论：对于任意三个整数 i,j,k 满足 1\le i,j\le n,i\neq j，将 a_i 加上 ka_j，b_i 加上 kb_j 后答案不变。

证明的话好像所有能搜到的题解都说显然，我也不太清楚，就讲个大概思路吧。

由于原点已经是一个给定的点，根据题目限制从原点沿一个方向走若干步和从另一个点沿同样方向走同样步到达的点颜色相同。而根据前面一维的做法最优方法中循环的矩阵不会出现两种颜色，所以 (a_i,b_i) 和 (a_i+a_j,b_i+b_j) 是等价的。同理可以得到上述结论正确。

例如下面这张图，点 A 和点 B 实际是等价的。

接着考虑根据这个性质将题目简化，将二维的问题根据这个结论变成一维。注意到 (a_i+ka_j,b_i+kb_j) 类似于辗转相除法，所以可以考虑将第一维消成 0。这样我们就将这 n 个点的坐标变成 1 个 (0,0)，n-2 个 (a,0)，和一个 (x,y)。按照第一维求出这个矩阵的水平长度，其竖直长度维 y，两者相乘即可。