题解：AT_arc219_d [ARC219D] Grid Game

· · 题解

挺简单的。

思路

公平组合游戏。

我们将棋盘上的格子按 (i+j) 的奇偶性分层进行处理。

对于每个格子 (i,j)，他的权值是：

$w(i,j) = 0$，当 $(i+j) \bmod 2 = 0$。 再计算总的异或和： $sg = \bigoplus_{i=1}^{n} \bigoplus_{j=1}^{n} w(i,j)$。 - 若 $sg \not= 0$，则 Alice 获胜； - 若 $sg = 0$，则 Bob 获胜。 那总结上面的就是如下这个数学推导出的结论： $sg=\bigoplus\limits_{i=1}^n\bigoplus\limits_{j=1}^n \left( A_{i,j}\bmod (K+1) \right) \cdot [(i+j)\bmod 2=1]

若 sg\neq0 则 Alice 胜，否则 Bob 胜。

:::info[AC code]

#include <bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 4e6 + 7;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
// const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
// const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int dx[] = {-1 , 1 , 0 , 0} ;
const int dy[] = {0 , 0 , -1 , 1} ;

inline int read ()
{
    int s = 0 , w = 1 ;
    char ch = getchar () ;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar () ;
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0' ;
        ch = getchar ();
    }
    return s * w ;
}
inline void write (int x)
{
    if (x < 0) putchar ('-') , x = -x ;
    if (x > 9) write (x / 10) ;
    putchar (x % 10 + '0') ;
    return ;
}

signed main()
{
    fst ;
    int t ;
    cin >> t ;
    while (t --)
    {
        int n ;
        int k ;
        cin >> n >> k ;
        int s = 0 ;
        for (int i = 1 ; i <= n ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                int a ;
                cin >> a ;
                if ((i + j) & 1)
                {
                    s = s ^ (a % (k + 1)) ;
                }
            }
        }
        if (s)
        {
            cout << "Alice" ;
        }
        else
        {
            cout << "Bob" ;
        }
        cout << endl ;
    }
    return 0;
}

:::