AT_wtf19_c2 Triangular Lamps Hard 题解

· · 题解

:::::info[题目基本信息] 考察：构造，Ad-hoc，数位 DP，二分，倍增（无评分）。
题目简介：
一个网格图，原来上面有一个黑点 (X,Y)，然后你进行了下面的操作若干次：

最终有 n 个黑点，以 \{x_n\},\{y_n\} 的形式给出，求最开始的 X,Y。
数据范围：

时间限制：4s。
空间限制：1G。
::::: :::::info[闲话] 这题是人能想到的？？？
没有人类了。
可以数数本篇文章有多少“注意到”。
::::: 注意到这个题没有像 CF2096D 那样优美的性质，所以这个题直接做超级难做，所以我们考虑转到一条直线上，就取 Y=-10^{17} 吧。
注意到我们将这些点通过操作转化到 Y=-10^{17} 这条线上来，具体地，若黑点为 (0,0)，那么令 x=0,y=-1，让 (0,0) 变为白点，(0,-1) 和 (1,-1) 变为黑点。
这时我们注意到一个点被贡献奇数次才能真正被贡献，所以若 (X,Y) 会被贡献成黑点，那么 \dbinom{y_i-Y}{X-x_i}\equiv 1\pmod 2，通过这里提到的引理可以得到 X-x_i\subseteq y_i-Y（二进制意义下，下同）。
注意到这一些黑点所贡献在这条直线上的黑点与原点所贡献的相同，所以我们找到这些黑点中的最左点和最右点就可以确定原点坐标了。
这样时间复杂度为 \Theta(nV)，显然过不去。
注意到我们并不需要找到所有贡献到这条直线上的黑点，找到最左点和最右点就足够了，所以我们考虑如何找到这两点。
注意到最左点的 X_l-x_i=0，最右点的 X_r-x_i=y_i-Y，其余黑点的 X-x_i\subseteq y_i-Y，所以我们得到 X_l-x_i\subseteq X-x_i\subseteq X_r-x_i，所以得到一个黑点后我们可以倍增求出最左点和最右点。
现在我们只需要得到一个落在直线上的黑点。
观察翻转的点注意到 (x,y),(x,y+1),(x+1,y) 这些点的 (x-y)\bmod 3 都是不同的，同时由于最开始只有一个点，所以必定有一个 (x-y)\bmod 3 满足点数是奇数。
这有什么用呢？
注意到一段区间内点数的奇偶性是好算的，直接数位 DP 即可，所以我们考虑二分。
具体地，定出一个足够大的区间（列不等式算一算可以得到是 [-V,3V]），然后选中点判断两边的奇偶性，由于总点数是奇数所以必定有一边是奇数，然后就可以找出一个黑点了。
然后就做完了。
时间复杂度为 \Theta(n\log^2 V)，空间复杂度为 \Theta(n+\log V)。

code