【World tour final 2019 C1】Triangular Lamps Easy 做题记录

有一个无限大的平面，每个点上都有一盏灯。

刚开始只有位于 $(X,0)$ 的灯是亮起的，之后 Alice 会进行若干次操作，每次操作她会选择一个位置 $(x,y)$，并同时改变 $(x,y)$、$(x,y-1)$、$(x-1,y-1)$ 这些灯的状态。

最终一共有 $n$ 盏灯亮起了，给定这些灯的位置 $(x_i,y_i)$，请你求出 $X$。

$1\le n\le 10^5$，$0\le |x_i|,|y_i|\le 10^{17}$。

保证有解且 $0\le |X| \le 10^{17}$

由于操作可逆，所以考虑不断把亮着的灯往下移，对于一盏亮着的灯 $(x,y)$，可以操作一次 $(x,y)$ 来让它灭掉，同时改变 $(x,y-1)$ 和 $(x-1,y-1)$ 的状态。

设 $f_{x,y}$ 表示 $(x,y)$ 这盏灯在通过以上操作灭掉 $x'>x$ 的灯时的状态，那么有 $f_{x,y}=f_{x,y+1}\oplus f_{x+1,y+1}$。不难发现 $f_{x,y}=\binom{X-x}{0-y}\operatorname{mod} 2$。那么根据 Lucas 定理，有 $f_{x,y}=[X-x\in -y]$，其中 $\in$ 为二进制意义下的包含，即 $X-x$ 按位与 $-y$ 还是 $X-x$。

由于操作可逆，所以 Alice 的操作可以看作先把亮的灯往下移下的地方再把亮的灯往上移，所以对于一个足够小的 $y$，有 $f_{x,y}=\oplus_{i=1}^n [x_i-x\in y_i-y]$。

那么假如已经找到了一组 $(p,y)$ 满足 $f_{p,y}=1$，则可以得知 $p-X\in -y$。那么可以从大往小枚举 $k$，若 $f_{p-2^k,y}=1$ 则让 $p\to p-2^k$。这样最终会把 $p-X$ 变成 $0$，得到 $X$。

而由于刚开始亮着的灯是 $(X,0)$，所以 $f_{10^{17},-(2^{60}-1)}$ 一定为 $1$，那么令 $p=10^{17}$，$y=-(2^{60}-1)$ 即可。

代码如下：

// Problem: Triangular Lamps Easy
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_wtf19_c1
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

struct node
{
	long long x,y;
}a[S];

int n;

inline bool chk(long long x,long long y)
{
	bool res=false;
	for(int i=1;i<=n;i++) res^=((a[i].y-y)&(x-a[i].x))==x-a[i].x;
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
	long long p=100000000000000000ll,y=-((1ll<<60)-1);
	printf("%d\n",chk(p,y));
	for(int i=59;i>=0;i--)
	{
		if(chk(p-(1ll<<i),y)) p-=1ll<<i;
	}
	printf("%lld\n",p);
	return 0;
}