题解：AT_arc148_d [ARC148D] mod M Game

Kibrel · 2026-07-27 10:39:12 · 题解

如果通过审核了这会是我的第一篇题解。

我们注意到先手胜利是不好判断的，那么我们就可以去判断后手是否能够胜利。

当

的时候后手可以胜利， 而且必然有 A + B \equiv \sum a_i \pmod m 。

然后你可以得到本题最重要的性质：

我们作为后手，需要保证这个性质且做到每一步都能够跟随先手。也就是说, 需要保证 2a_i \bmod m 的个数是偶数个，我们必然可以做到跟随先手令 A \equiv B 。

于是我们需要判断：

均满足，后手胜利。否则先手胜利。

Talk is cheap, show you the code.

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

namespace OI {

#define int long long
#define endl "\n"

int n, m;
map<int, int> bucket;

void main() {
    cin >> n >> m;
    int sum = 0;
    for (int i = 1; i <= 2 * n; i++) {
        int a;
        cin >> a;
        sum = (sum + a) % m;
        bucket[2 * a % m]++;
    } 
    int newS = 0;
    for (auto p : bucket) {
        if (p.second & 1) {
            puts("Alice");
            return;
        }
        newS = (newS + p.first * p.second / 2) % m;
    }
    if (newS == sum)
        puts("Bob");
    else
        puts("Alice");
}

#undef int
#undef endl

}

int main() {
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(0);

    OI::main();

    return 0;
}