[Codeforces 100365F][SG value] Coins Game

原題連結
相當經典的一題SG value

難點在於看出此題每個格子是獨立的遊戲，這需要透過模型轉換和數學歸納法證明。

不妨先接受這個結論，那麼我們變成要求每個是'1'的格子的SG value的XOR，怎麼求呢？

注意到N,M都<=50，那麼最多就只有N*M個格子，每個格子最多有N*M個轉移，所以如果直接用定義去計算SG value的話也只需要O(N^2*M^2)，時間上是可以忍受的。

最後一個細節是如何輸出先手的第一步，這可以在計算SG時同步完成，但是我採用的懶人方法就是在要輸出的時候重新枚舉一次，反正複雜度還是O(N^2*M^2)～～輕鬆過~~

yee~~

#include<bits/stdc++.h>
using namespace std;
const int maxn=50+5;
const int maxm=50+5;
int SG[maxn][maxm];
int getSG(int i,int j)
{
    if(i==0 || j==0) return 0;
    if(SG[i][j]!=-1) return SG[i][j];
    set<int> S;
    for(int ip=0;ip<i;ip++)
        for(int jp=0;jp<j;jp++) S.insert(getSG(i,jp)^getSG(ip,j)^getSG(ip,jp));
    for(int ans=0;;ans++) if(!S.count(ans)) return SG[i][j]=ans;
}
char s[maxn][maxm];
int main()
{
    freopen("coins.in","r",stdin);
    freopen("coins.out","w",stdout);
    memset(SG,-1,sizeof SG);
//    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) printf("SG[%d][%d]:%d\n",i,j,getSG(i,j));
    int N,M,SGall=0;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        scanf("%s",&s[i][1]);
        for(int j=1;j<=M;j++) if(s[i][j]=='1') SGall^=getSG(i,j);
    }
//    printf("SGall=%d\n",SGall);
    printf("%s\n",SGall!=0?"Ann":"Betty");
    if(SGall)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++) if(s[i][j]=='1')
                for(int ip=0;ip<i;ip++)
                    for(int jp=0;jp<j;jp++) 
                        if((SGall^getSG(i,j)^getSG(i,jp)^getSG(ip,j)^getSG(ip,jp))==0) 
                            {printf("%d %d\n%d %d\n",i,j,ip,jp);return 0;}
}