【CF662A】Gambling Nim
题意：n长卡牌，第i张卡牌正面的数字是$a_i$，反面的数字是$b_i$，每张卡牌等概率为正面朝上或反面朝上。现在Alice和Bob要用每张卡牌朝上的数字玩NIM游戏，问先手获胜的概率。
$n\le 5000,a_i,b_i\le 10^{18}$
题解：傻逼题都不会了，先令所有的都是正面朝上，再令$S=a_1\ \text{xor}\ a_2...a_n,c_i=a_i\ \text{xor}\ b_i$，则问题变成了选出一些$c_i$使得异或和为$S$的概率。显然搞基一发，然后将S放到线性基里消一下。如果能消没，则概率为$1-{1\over 2}^{siz}$，siz是线性基大小。否则概率是1。
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
typedef long long ll;
const int maxn=500010;
int n,m;
ll S,v[maxn];
inline ll rd()
{
ll ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,j;
ll a,b;
for(i=0;i<n;i++) a=rd(),b=rd(),S^=a,v[i]=a^b;
for(i=60;i>=0;i--)
{
for(j=m;j<n;j++) if((v[j]>>i)&1) break;
if(!((v[j]>>i)&1)) continue;
if(m!=j) swap(v[m],v[j]);
for(j=0;j<n;j++) if(j!=m&&((v[j]>>i)&1)) v[j]^=v[m];
m++;
}
for(i=0;i<m;i++) if((S^v[i])<S) S^=v[i];
if(S) puts("1/1");
else printf("%lld/%lld",(1ll<<m)-1,1ll<<m);
return 0;
}//4 1 2 2 4 4 8 8 1