[CF 494E] Sharti

作法：

詳細的作法在官方解已經講的很清楚了，這裡講一下為什麼 grundy number 長那樣的證明。

首先考慮$k$是無限大的情形，也就是這個遊戲可以選擇任意大的正方形，我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的，以下用數學歸納法，假設以$(1,1)$為左上角，$(x,y)$為右下角的矩形中，除了$(x,y)$以外的格子的 grundy number 都知道了，並且設$(x,y)$這格的理論值為$2^i$，那麼我們要證明兩件事：「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$，還有有出現$0,1,...,2^i-1$。

首先是沒有出現$2^i$，因為他的後繼狀態是一個正方形的每格裡都有一個石頭，除了$(x,y)$那格，因此這個命題就可以等價為：考慮一張方格表，上面寫上每個格子的理論上的 grundy number ，則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法，如果某一塊正方形內所有的數 xor 起來等於$0$，因為格子中的數都是$2$的冪次，所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$，設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量，那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$，而因為對於每個$i$，這塊正方形中的$2^i$都是偶數個，所以所有$a_i$的奇偶性相同，當$i$足夠大時$a_i$顯然$=0$，因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$，其中$y$是奇數，那麼不難證明$a_y$是奇數，矛盾。

再來是證明出現了$0,1,...,2^i-1$（其中$0$是顯然的），這可以用數歸解決，假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的，那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊，那麼對於任意一個落在左下角那塊的格子$(x,y)$來說，考慮$(x-2^r,y)$，可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達，所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理，除了$(2^{r+1},2^{r+1})$這一格，我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時，因為整張表格是沿對角線對稱的，所以兩邊的 xor 值會抵消，只剩下對角線上的，此時就化為一維的問題了，也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話，令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$，則$S$裡出現了$1,2,...,2^{r+1}-1$（其中$\bigoplus $代表 xor 運算）。這件事的證明可以對$r$數歸，還算蠻顯然的所以略去，因此這樣成功證完$k$是無限大的情形了。

當$k$不是無限大時其實也類似，一樣也是先考慮每個格子的理論值形成的表，證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是，假設$t$滿足$2^t\leq k<2^{t+1}$，那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的，證法和剛才類似，這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了，因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格，所以顯然是對的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
struct rec
{
    int x1,y1,x2,y2 ;
    void scan(){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);}
}r[maxn],r2[maxn];
 
struct P
{
    int x,d,u,val ;
    bool operator < (const P &rhs) const
    {
        return x<rhs.x ;
    }
}ev[maxn];
 
int ST[4*maxn],tag[4*maxn] ;
vector<int> v ;
void modify(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R) { tag[id]+=val ; return ; }
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,2*id,val) ;
    else if(l>=mid) modify(l,r,mid,R,2*id+1,val) ;
    else
        modify(l,mid,L,mid,2*id,val) ,
        modify(mid,r,mid,R,2*id+1,val) ;
    ST[id]= (tag[2*id] ? v[mid]-v[L] : ST[2*id]) +
            (tag[2*id+1] ? v[R]-v[mid] : ST[2*id+1]) ;
    ST[id]%=2 ;
}
 
int getarea(int num)
{
    if(!num) return 0 ;
    memset(ST,0,sizeof(ST)) ;
    memset(tag,0,sizeof(tag)) ;
    v.clear() ;
    for(int i=0;i<num;i++) v.push_back(r2[i].y1) , v.push_back(r2[i].y2+1) ;
    sort(v.begin(),v.end()) ;
    v.resize(unique(v.begin(),v.end())-v.begin()) ;
    for(int i=0;i<num;i++)
    {
        int id1=lower_bound(v.begin(),v.end(),r2[i].y1)-v.begin() ;
        int id2=lower_bound(v.begin(),v.end(),r2[i].y2+1)-v.begin() ;
        ev[2*i]=(P){r2[i].x1,id1,id2,1} ,
        ev[2*i+1]=(P){r2[i].x2+1,id1,id2,-1} ;
    }
    sort(ev,ev+2*num) ;
    int x=0 , val=0 , ret=0 ;
    for(int i=0;i<2*num;i++)
    {
        ret+=(ev[i].x-x)*val ; ret%=2 ;
        modify(ev[i].d,ev[i].u,0,maxn-1,1,ev[i].val) ;
        x=ev[i].x ;
        val=ST[1] ;
    }
    return ret ;
}
 
int a[60] ;
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=0;i<m;i++)  r[i].scan() ;
 
    int i=0 ;
    for(int j=1;j<=k;i++,j*=2)
    {
        int cnt=0 ;
        for(int z=0;z<m;z++)
        {
            int x1=(r[z].x1-1)/j+1 , y1=(r[z].y1-1)/j+1 ;
            int x2=r[z].x2/j , y2=r[z].y2/j ;
            if(x1>x2 || y1>y2) continue ;
            r2[cnt++]=(rec){x1,y1,x2,y2} ;
        }
        a[i]=getarea(cnt) ;
    }
    for(int j=0;j<i;j++)
    {
        a[j]=(a[j]-a[j+1]+2)%2 ;
        if(a[j]){printf("Hamed\n") ; return 0 ;}
    }
    printf("Malek\n") ;
}