BZOJ-3105: 新Nim游戏 (nim博弈&线性基)

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000;
ll ans,sum; int a[maxn],base[maxn];
int main()
{
    int N; scanf("%d",&N);
    rep(i,1,N) scanf("%d",&a[i]),sum+=a[i];
    sort(a+1,a+N+1);
    for(int i=N;i>=1;i--){
        int tmp=a[i];
        for(int j=30;j>=0;j--){
            if(a[i]&(1<<j)){
                if(!base[j]){
                    base[j]=a[i];
                    break;
                }
                else a[i]^=base[j];
            }
        }
        if(a[i]) ans+=tmp;
    }
    printf("%lld\n",sum-ans);
    return 0;
}