[SPOJ MATGAME]MATGAME - Matrix Game

先備知識：$SG$函數的性質

首先可以發現每一列(這裡的「列」是row)可以視作獨立的遊戲，那麼我們就可以分別把每一列的$SG$函數算出來，全部XOR起來，如果是零，那麼先手敗，否則先手勝

再來觀察每一列的$SG$函數怎麼算，為了方便說明，設這一列的第$i$個數字是$A_{i}$，$SG(i)$代表$A_{1}$～$A_{i-1}$都是0時的$SG$函數

經過觀察，可以發現：
$SG(M)=A_{M}$(代表一個經典的$Nim$遊戲)
$if\ A_{i}\leq SG(i+1)$，$SG(i)=A_{i}-1$
$else$，$SG(i)=A_{i}$
(也是一個$Nim$遊戲，只是0顆石頭時的$SG$函數是$SG(i+1)$，不是0)

把所有$SG(1)$XOR起來，判斷是不是0，就完成了

時間複雜度：$O(N*M)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
using namespace std;
int N,M;
int GetSG(const int cnt,const int sg_of_zero)
{
    assert(cnt>0);
    if(cnt<=sg_of_zero)return cnt-1;
    return cnt;
}
int GetSG(const vector<int>&s)
{
    int ans=0;
    for(int i=(int)s.size()-1;i>=0;i--)ans=GetSG(s[i],ans);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&M);
        int ans=0;
        for(int row=0;row<N;row++)
        {
            vector<int>s;
            for(int col=0,v;col<M;col++)
            {
                scanf("%d",&v);
                if(v)s.push_back(v); 
            }
            ans^=GetSG(s);
        }
        puts(ans==0?"SECOND":"FIRST");
    }
    return 0;
}