hdu 3032 Nim or not Nim?

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=3032

简要题意：给 $n$ 堆石子，每次操作可以 $n$ 堆石子中取若干个石子或者将一堆石子数大于等于 $2$ 的石子分成两堆石子

$n\le {10}^6$

Solution

最经典的 $multi-sg$，但是并没有什么有用的结论，所以我们直接打表找规律即可，能够得到

$$SG(x)=\{\begin{array}{c}x-1，x\mathrm{mod}4=0\\ x，x\mathrm{mod}4=1or2\\ x+1，x\mathrm{mod}4=3\end{array}$$

#include <iostream>
#define maxn 1000010
using namespace std;

int n, a[maxn];

void work() {
    cin >> n; int sgsum = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        switch (a[i] % 4) {
        case 0 : sgsum ^= a[i] - 1; break;
        case 1 :
        case 2 : sgsum ^= a[i]; break;
        case 3 : sgsum ^= a[i] + 1; break;
        }
    } cout << (sgsum ? "Alice" : "Bob") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
}