题解：UVA1482 Playing With Stones

结论：$\mathrm{SG}(x)=\begin{cases}\frac{x}{2} & x\bmod 2=0 \\ \mathrm{SG}(\frac{x-1}{2}) & x\bmod 2=1\end{cases}$

• $x\bmod 2=0$：$\mathrm{SG}(x)=\mathrm{mex}\{\mathrm{SG}(\frac{x}{2}),\dots,\mathrm{SG}(x-1)\}$，
  设 $S$ 为 $x$ 的转移点集合，
  • 对于 $y\in S,y\bmod 2=0$，$\mathrm{SG}(y)$ 覆盖 $[\lceil\frac{x}{4}\rceil,\frac{x}{2}]$；
  • 对于 $y\in S,y\bmod 2=1$，发现这些 $y$ 对应的 $\frac{y-1}{2}$ 构成 $z$ 的转移点，其中 $z=\begin{cases}\frac{x}{2}+1 & \frac{x}{2}\bmod 2=1 \\ \frac{x}{2} & \frac{x}{2}\bmod 2=0\end{cases}$，（特别的，如果 $\frac{x}{2}$ 是奇数，那么 $\frac{\frac{x}{2}-1}{2}$ 不是 $z$ 的转移点，那么 $z$ 会缺一个转移点 $z-1$，但由于 $\mathrm{SG}(\frac{\frac{x}{2}-1}{2})=\mathrm{SG}(z-1)$，因此不影响）。
  因此 $x\bmod 2$ 时结论成立。
• $x\bmod 2=1$：这时 $x$ 相对于 $x-1$ 的转移点来说，少了一个 $\frac{x-1}{2}$，多了一个 $x-1$，因此 $\mathrm{SG}(x)=\mathrm{SG}(\frac{x-1}{2})$。

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

const int N = 1e2 + 5;

int n;

LL SG(LL a) {
    while (a & 1) {
        a = ((a - 1) >> 1);
    }
    return (a >> 1);
}

void solve() {
    cin >> n;
    LL a, sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        sum ^= SG(a);
    }
    cout << (sum ? "YES\n" : "NO\n");
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}