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

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

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

最终一共有 nn 盏灯亮起了,给定这些灯的位置 (xi,yi)(x_i,y_i),请你求出 XX

1n1051\le n\le 10^50xi,yi10170\le |x_i|,|y_i|\le 10^{17}

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

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

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

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

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

而由于刚开始亮着的灯是 (X,0)(X,0),所以 f1017,(2601)f_{10^{17},-(2^{60}-1)} 一定为 11,那么令 p=1017p=10^{17}y=(2601)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;
}