## 【Codeforces 662A】Gambling Nim

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

const int N = 500000+9;
const int SGZ = 61+9;

int n,cnt;
LL a[N],b[N],bas[SGZ],sum;

char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline bool insert(LL w) {
for (int i=61;~i;i--) if (w&(1LL<<i)) {
if (bas[i]) {
w ^= bas[i];
} else {
bas[i] = w;
return true;
}
}
return false;
}

inline LL pow(LL w, int t) {
LL ret = 1;
while (t) {
if (t & 1) ret *= w;
w *= w; t >>= 1;
}
return ret;
}

int main(){
for (int i=1;i<=n;i++) {
sum ^= a[i];
cnt += insert(a[i] ^ b[i]);
}
if (!cnt && !sum) {
puts("0/1");
} else if (insert(sum)) {
puts("1/1");
} else {
printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt));
}
return 0;
}


## 【BZOJ 2844】albus就是要第一个出场

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

const int MOD = 10086;
const int N = 100000+9;
const int SGZ = 30+9;

int n,m,arr[N],bas[SGZ],cnt,vout;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline bool insert(int w) {
for (int i=30;~i;i--) if (w&(1<<i)) {
if (bas[i]) {
w ^= bas[i];
} else {
bas[i] = w;
return true;
}
}
return false;
}

inline int pow(int w , int t) {
int ret = 1;
while (t) {
if (t&1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}

int main(){
for (int i=1;i<=n;i++) {
cnt += insert(arr[i]);
}
for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) {
cnt--;
if (m&(1<<i)) {
vout += tmp * (1LL<<cnt) % MOD;
vout %= MOD;
}
}
printf("%d\n",(vout+1)%MOD);
return 0;
}


## 【HDU 3949】XOR

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

const int N = 10000+9;

int n,bas[70],cnt,m;
LL arr[N],l,r,STA,tag;

inline void insert(LL &w, int num) {
for (int i=61;~i;i--) if (w & (1LL<<i)) {
if (bas[i]) {
w ^= arr[bas[i]];
} else {
bas[i] = num;
break;
}
}
if (!w) tag = 1;
}

inline LL cal(LL w) {
LL ret = 0;
for (int i=0,cur=0;i<cnt;i++) {
while (!bas[cur]) cur++;
if (w&(1LL<<i)) ret ^= arr[bas[cur]];
cur++;
}
return ret;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){
printf("Case #%d:\n",tot);
memset(bas,0,sizeof(bas));
memset(arr,0,sizeof(arr));
cnt = tag = 0;

for (int i=1;i<=n;i++) {
cin>>arr[i];
insert(arr[i],i);
}

for (int i=0;i<=61;i++) if (bas[i]) {
++cnt;
for (int j=i+1;j<=61;j++) if (bas[j]) {
if (arr[bas[j]] & (1LL<<i)) {
arr[bas[j]] ^= arr[bas[i]];
}
}
}

m = read(); STA = (1LL<<cnt) - 1;
for (int i=1;i<=m;i++) {
LL tmp; scanf("%I64d",&tmp); tmp -= tag;
if (STA < tmp) puts("-1");
else printf("%I64d\n",cal(tmp));
}
}
return 0;
}


## 【BZOJ 3569】DZY Loves Chinese II

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

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971;
const int SGZ = 40;

int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 1;
}

void DFS1(int w, int f) {
vis[w] = 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (vis[to[i]]) {
int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
sym[w] ^= W; sym[to[i]] ^= W;
} else DFS1(to[i],w);
}
}

void DFS2(int w, int f) {
for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i])
DFS2(to[i], w), val[i] ^= sym[to[i]],
val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
if (!bas[i]) {bas[i] = tmp; return false;}
else {tmp ^= bas[i]; if (!tmp) return true;}
} return val[w]?false:true;
}

int main(){
DFS1(1,1); DFS2(1,1);
k = read(); tag = 1; memset(bas,0,sizeof(bas));
for (int i=1;i<=k;i++) c[i] = read()^cnt;
for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
if (tag) puts("Connected"), cnt++;
}
return 0;
}


## 【BZOJ 4004】[JLOI2015] 装备购买

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

const int N = 500+9;
const int MOD = 1000000007;

int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout;

inline int read(){char c=getchar(); int ret=0,f=1;while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret*f;}
inline bool cmp(const int a, const int b) {return cost[a] < cost[b];}

inline void update(int w) {
for (int i=1;i<=m;i++) if (f[w][i]) {
if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;}
else {
int t2 = f[bas[i]][i], t1 = f[w][i];
for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD;
}
}
}

int main(){
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read();
for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i;
sort(num+1,num+1+n,cmp);
for (int i=1;i<=n;i++) update(num[i]);
printf("%d %d\n",cnt,vout);
return 0;
}


## 【BZOJ 3105】[cqoi2013] 新Nim游戏

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

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int bas[32],arr[109];
inline bool update(int w) {
for (int i=0;i<=31;i++) if (w & 1<<i)
if (bas[i]) w ^= bas[i];
else {bas[i] = w; return 1;}
return 0;
}

int main(){
int k = read(); LL vout = 0;
for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i];
sort(arr+1,arr+1+k);
for (int i=k;i;i--) vout -= update(arr[i])*arr[i];
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 4568】[Scoi2016] 幸运数字

《浅谈省选的时候还不会线性基的悲伤有多大》

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

const int N = 20000+9;

LL arr[N];

inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

namespace LCA{
int fa[N][16],dep[N];
LL f[N][16][61],POW[61];

void DFS(int w, int f) {
fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}

inline void merge(LL *a, LL *b) {
for (int i=60;~i;i--) if (b[i]) {
LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
if (!a[j]) {a[j] = w; break;}
else w ^= a[j];
}
}
}

inline void init() {
for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
for (int i=1;i<=n;i++) for (int j=2;j<=15;j++)
fa[i][j] = fa[fa[i][j-1]][j-1],
memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
merge(f[i][j],f[fa[i][j-1]][j-1]);
}

inline LL query(int x, int y) {
static LL bas[61]; memset(bas,0,sizeof(bas));
if (dep[x] < dep[y]) swap(x,y);
for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y])
merge(bas,f[x][i]), x = fa[fa[x][i]][1];
if (x == y) merge(bas,f[x][0]);
else {
for (int i=15;~i;i--)  if (fa[x][i] != fa[y][i])
merge(bas,f[x][i]), merge(bas,f[y][i]),
x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
merge(bas,f[x][0]);
} LL ret = 0;
for (int i=0;i<=60;i++) if (bas[i])
for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
for (int i=0;i<=60;i++) ret ^= bas[i];
return ret;
}
};

int main(){
for (int i=1;i<=n;i++) arr[i] = readL();
LCA::DFS(); LCA::init();
return 0;
}


## 【BZOJ 4269】再见Xor

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;

int n,arr[MAXN],cnt;

inline void Gauss(){
for (int k=31;k;k--){
int w = 1<<(k-1), pos;
for (pos=cnt+1;pos<=n;pos++)
if (arr[pos]&w) break;
if (pos==n+1) continue;
else {
swap(arr[++cnt], arr[pos]);
for (int i=1;i<=n;i++)
if (i!=cnt && (arr[i]&w))
arr[i] ^= arr[cnt];
}
}
}

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&arr[i]);
Gauss(); int vout = 0;
for (int i=1;i<=cnt;i++) vout ^= arr[i];
printf("%d ",vout);
printf("%d\n",vout ^= arr[cnt]);
return 0;
}