本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-28 21:14:58

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

• 选定 $x,y$，让 $(x,y),(x,y+1),(x+1,y)$ 中黑点变成白点，白点变成黑点。

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

• $1\le n\le 10^4$。
• $\forall i\in[1,n],|x_i|,|y_i|\le 10^{17}$。
• 保证有唯一解。

时间限制：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