Description

有一个 \(n*n\) 的矩形,给出 \(m\) 个子矩形,这些矩形内部的点都是白色的,其余的点都是黑色,每一次你可以选择一个变长不超过 \(k\) 的正方形,满足这个正方形的右下角是白色的,并将这个正方形内的颜色取反

两个人轮流操作,不能操作者输,求是否先手必胜

Solution

这是翻硬币游戏的模型,用到结论:局面的 \(SG\) 值等于局面中每个正面朝上的棋子单一存在时的 \(SG\) 值的异或和

这样就可以打一个表找规律

打表发现这个题的 \(SG[i][j]=min(lowbit(i),lowbit(j),maxbit(k))\)

然后就只需要把所有白点的 \(SG[i][j]\) 异或起来看是否为 \(0\) 就好了

可以用扫描线维护,一种直接的做法是考虑每一个二进制为作为 \(lowbit\) 时的贡献

一个二进制位 \(i\) 作为 \(lowbit\) 的特点是:

1.低位不能有 \(1\)

2.\(i\) 这一位为 \(1\)

3.\(i\) 的高位的随便选

因为是求异或和,所以 \(lowbit(i)\) 出现了偶数次的话,贡献就可以抵消了,所以只需要出现偶数次的二进制了

把行列分开考虑,扫描线处理,列用线段树维护,最后再将行和列合并

考虑算出一个区间 \([l,r]\) 的 \(lowbit\) 的异或和

\(i\) 作为 \(lowbit\) 出现的次数是 \(\frac{r}{i}-\frac{l-1}{i}-(\frac{r}{i<<1}-\frac{l-1}{i<<1})\)

后面减去的是 \(i\) 这一位不为 \(1\) 的方案数

最后再将行列合并就行了

依旧是考虑每一位作为 \(lowbit\) 出现的次数,注意合并时是将行的 \(lowbit\) 和 列的 \(lowbit\) 取 \(min\)

#include 
    
     using namespace std;const int N=1e5+10;inline int gi(){    register int str=0;register char ch=getchar();    while(ch>'9' || ch<'0')ch=getchar();    while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();    return str;}struct node{    int x,l,r,d;    bool operator <(const node &p)const{return x
     
      >1;    if(se<=mid)Modify(tr[o].ls,l,mid,sa,se,t);    else if(sa>mid)Modify(tr[o].rs,mid+1,r,sa,se,t);    else Modify(tr[o].ls,l,mid,sa,mid,t),Modify(tr[o].rs,mid+1,r,mid+1,se,t);    upd(o);}int main(){    cin>>n>>m>>k;    for(K=1;K<=k;K<<=1);    int xl,xr,yl,yr,cnt=0,x,y,sum=0,ans=0;    for(int i=1;i<=m;i++){        xl=gi();yl=gi();xr=gi();yr=gi();        e[++cnt]=(node){xl,yl,yr,1};        e[++cnt]=(node){xr+1,yl,yr,-1};    }    sort(e+1,e+cnt+1);    for(int i=1;i<=cnt;i++){        if(e[i].x!=e[i-1].x){           x=lowbit(e[i-1].x,e[i].x-1);y=tr[rt].w;            xl=xr=sum=0;            for(int j=K;j;j>>=1){                sum=-xl*xr;xl+=((x&j)>0);xr+=((y&j)>0);sum+=xl*xr;                if(sum&1)ans^=j;            }        }        Modify(rt,1,n,e[i].l,e[i].r,e[i].d);    }    if(ans)puts("Hamed");    else puts("Malek");    return 0;}