[Codeforces g100365F][ASC 34]Coins Game

原文題目敘述 (第7頁)
傳code

題目敘述：
桌上擺了N*M個硬幣 (位置從 (1,1) 到 (N,M) )，一開始知道哪些硬幣頭朝上，哪些數字朝上
每一回合必須選一個頭朝上的硬幣 (假設這個硬幣的位置是 (i,j) )，再選個位置 (a,b)，其中0<=a<i且0<=b<j，然後把 (a,b)、(a,j)、(i,b)、(i,j) 這四個位置的硬幣都翻轉
注意到，當a=0或b=0的時候，有些要翻轉的位置是不存在的，所以在這些位置的翻轉操作是無效的
當玩到最後每個硬幣都是數字朝上，沒有步可以動了，就輸了

故事背景：
某校的學生餐廳是孳殉懊淋霹啞界聞名的 (以下簡稱學餐)
有時食物吃下去會發現又酸又澀的酒味，然後就知道，又要拉肚子一整天了
還有一次吃高麗菜結果被魚刺卡喉嚨，馬上緊急送醫 (造成食道傷口，還好沒傷到喉嚨)
我們從此對學餐感到恐慌，因此合力爭取到晚餐不吃學餐的權利 (不過預算只有100元，而且午餐還是無法倖免)
然後這是某次培訓時想出來的遊戲
因為需要很多很多的硬幣鋪在桌上，所以想要申請經費補助
但是管經費的說他為了讓我們不吃學餐幫我們墊錢 (100元*4人*21天)，郵局帳戶見底了，所以拒絕請求
我們只好寫程式用電腦來模擬這個硬幣遊戲了
後來覺得太無聊，寫了AI來對打
注意到，國手雖然很可憐每天都要被逼著吃學餐，可是他們寫出來的AI都是無懈可擊的
請問誰會贏？
（真實事件改編）
（N<=50，M<=50）

以下是題解

如果要看懂這個題解，請先了解組合賽局的$SG$函數和$Nim$和的性質

首先，每個頭朝上的硬幣可以視為一個獨立的遊戲
提示：想想$Nim$和的性質，翻轉硬幣相當於$XOR$ (還是一頭霧水？請參考這裡)

因此，我們就可以用$O(N^{2}M^{2}\log(NM))$的時間預處理出每個位置的$SG\ value$ (因為我計算$mex$的方法牽涉到排序，其實利用基數排序還可以把$\log$去掉)，然後就可以算出整個盤面的$SG\ value$了！

題目要求當先手贏的時候要輸出一種必勝策略
只要用$O(N^{2}M^{2})$的時間枚舉$i$、$j$、$i_{1}$和$j_{1}$，找到一組解讓$SG(i,j)\oplus SG(i_{1},j)\oplus SG(i,j_{1})\oplus SG(i_{1},j_{1})=$整個盤面的$SG\ value$就好了 ($\oplus$是$XOR$的符號)
對了，還有一個條件
你只能考慮一開始的盤面中位置$(i,j)$的硬幣是頭朝上的$(i,j)$

時間複雜度：$O(N^{2}M^{2}\log(NM)+N^{2}M^{2})$

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
int SG[51][51];
int R,C;
int main()
{
//    freopen("in.txt","r",stdin);
    freopen("coins.in","r",stdin);
    freopen("coins.out","w",stdout);
    for(int i=0;i<=50;i++)SG[i][0]=SG[0][i]=0;
    for(int r=1;r<=50;r++)for(int c=1;c<=50;c++)
    {
        vector<int>tmp;
        for(int i=0;i<r;i++)for(int j=0;j<c;j++)
        {
            tmp.push_back(SG[i][j]^SG[r][j]^SG[i][c]);
        }
        sort(tmp.begin(),tmp.end()),tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
        for(int &i=SG[r][c]=0;i<(int)tmp.size()&&tmp[i]==i;i++);
    }
    while(scanf("%d%d",&R,&C)==2)
    {
        int ans=0;
        static bool is_head_up[51][51];
        for(int r=1;r<=R;r++)for(int c=1;c<=C;c++)
        {
            char type=getchar();
            switch(type)
            {
                case'0':is_head_up[r][c]=false;break;
                case'1':ans^=SG[r][c],is_head_up[r][c]=true;break;
                default:c--;break;
            }
        }
        printf("%s\n",ans==0?"Betty":"Ann");
        if(ans!=0)
        {
//            printf("ans=%d,%d\n",ans,SG[3][3]);
            for(int r=1;r<=R;r++)for(int c=1;c<=C;c++)if(is_head_up[r][c])
            {
                for(int i=0;i<r;i++)for(int j=0;j<c;j++)
                {
                    if((SG[r][c]^SG[i][c]^SG[r][j]^SG[i][j])==ans)
                    {
                        printf("%d %d\n%d %d\n",r,c,i,j);
                        goto index_found;
                    }
                }
            }
            assert(0);
            index_found:;
        }
    }
    return 0;
}