AT_arc219_d 题解

Moya_Rao · 2026-06-02 21:30:04 · 题解

• 想了解更多有关 Nim 游戏和 SG 函数的知识？
  • 推荐阅读此文章，本篇题解也节选于此。

没绷住之 Bachet 套上阶梯 Nim 再塞进一个网格图里，什么神秘大嵌套啊。

先不考虑网格图，如果是 Bachet 套上阶梯 Nim 该怎么做呢？很简单的，我们把 Bachet 里的 \bmod (k+1) 做在阶梯 Nim 里的每个 a_i 上，再照常让奇数位的 a_i 异或起来判断就行。证明也是简单的，在阶梯 Nim 的基础上，如果对方移动了 x 枚石子且原堆含有 > k 枚石子时，我方可以在同样堆做同样动作移动 k+1 - x 枚石子，这样就等价于消除了对方操作。

那么，现在有了一个网格图，怎么办呢？也是简单的，想到黑白染色，就能发现每步操作都是在两个不同色格子之间互相移动，最后移动到 (1,1) 的值等价于被彻底移走。令 (1,1) 位置为黑格，则这等价于黑格为偶数位置、白格为奇数位置的带个数限制（即套上 Bachet 游戏）的阶梯 Nim 游戏，直接做就行了。更具体的，黑格是 (i+j) 为偶数的格子 (i,j) 而白格是 (i+j) 为奇数的格子 (i,j)。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
int T,n,k,sum;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    T=read();
    while(T--){
        n=read(),k=read(),sum=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int x=read()%(k+1);
                if((i+j)%2==1)sum^=x;
            }
        if(sum)cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！