Grid Game 3-angle 题解

· · 题解

题链：CF2045F - Grid Game 3-angle

*3000？可能没这么难，不过不妨碍他是一个神仙题，巴什博奕变种。

题目描述的已经很清楚了，就不复述一次了。

令 a_i 表示所有 (x, y) 满足 x \equiv i \pmod {k + 1} 的位置上石头数量模 k + 1 的异或和。

对同层考虑 SG 定理，单个格子考虑巴什博奕模型。

定理：如果所有 a_i 不全为 0，先手必胜，否则后手必胜。

我们尝试证明上述定理。

引理：如果所有 a_i 均为 0，操作一次之后一定存在 a_j 变得不为 0。

容易发现，对某个 x \equiv i 操作后，a_i 会变得非 0，因为操作的石子数是 [1, k]，模 k + 1 定然会变，所以 a_i 变得非 0 了。我们可以给 (x + j, y) 加 [0, k] 个石子，其中 j \in [1, k]，容易发现，无法使得 a_i 恢复非 0。

后手必然可以操作一次使得所有 a_i 变回非 0，这是很容易看出的。

因为 a_i 非 0，所以 a_i 必定有值，后手对 a_i 操作后 a_i 可以归零，对于所有 a_{(i+j) \bmod {k + 1}}(1 \le j \le k)，如果先手给一个位置添加了 t，后手在相同位置添加 k + 1 - t 即可。

综上，按照第一种定义，存在必胜和必败态转换，此题可以解决。

时间复杂度 O(M \log M)。

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k, k = k + 1;
    map<int, int> mp;
    for (int i = 1; i <= m; i ++ )
    {
        int r, c, a;
        cin >> r >> c >> a, a %= k, r %= k;
        if (mp.count(r)) mp[r] = mp[r] ^ a;
        else mp[r] = a;
    }
    int ans = 0;
    for (auto it : mp) ans |= it.second;
    if (ans) cout << "Anda\n";
    else cout << "Kamu\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}