题解｜新nim游戏题解

做法：线性基+贪心
先手必胜。 游戏的结论是所有数的和不为则先手胜。因为自己可以取一次来修改局面，对手也可以取一次来修改局面，那么现在的目标就变成了取走最少的石头堆，让剩下的石头没有一个非空子集的和为。
而线性基刚好满足这一性质。所以问题就变成了构造一个线性基，使其包含的石子数最多。这个将石子降序插入线性基即可。
这是强行两个结论拼起来的题...

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

#define ll long long
const int N = 100010;

ll ans = 0, a[N];

struct lb {
    int p[64];
    void insert(ll x) {
        ll now = x; 
        for(ll i = 63; i >= 0; --i) {
            if((x >> i) & 1LL) {
                if(p[i]) x ^= p[i];
                else {
                    p[i] = x;
                    ans -= now;
                    return;
                }
            }
        }
    }
} B; 

int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]), ans += a[i];
    sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) B.insert(a[i]);
    printf("%lld\n", ans);
}