有一个无限大的平面,每个点上都有一盏灯。
刚开始只有位于 的灯是亮起的,之后 Alice 会进行若干次操作,每次操作她会选择一个位置 ,并同时改变 、、 这些灯的状态。
最终一共有 盏灯亮起了,给定这些灯的位置 ,请你求出 。
,。
保证有解且
由于操作可逆,所以考虑不断把亮着的灯往下移,对于一盏亮着的灯 ,可以操作一次 来让它灭掉,同时改变 和 的状态。
设 表示 这盏灯在通过以上操作灭掉 的灯时的状态,那么有 。不难发现 。那么根据 Lucas 定理,有 ,其中 为二进制意义下的包含,即 按位与 还是 。
由于操作可逆,所以 Alice 的操作可以看作先把亮的灯往下移下的地方再把亮的灯往上移,所以对于一个足够小的 ,有 。
那么假如已经找到了一组 满足 ,则可以得知 。那么可以从大往小枚举 ,若 则让 。这样最终会把 变成 ,得到 。
而由于刚开始亮着的灯是 ,所以 一定为 ,那么令 , 即可。
代码如下:
// 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;
}