CodeForces

http://codeforces.com/problemset/problem/662/A

题目大意：

给定n(n <= 500000)张卡片，每张卡片的两个面都写有数字，每个面都有0.5的概率是在正面，各个卡牌独立。
求把所有卡牌来玩Nim游戏，先手必胜的概率。

(⊙o⊙)…由于本人只会在word文档里写公式，所以本博客是图片格式的。

 

Code

　　

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 500010;
ll a[maxn],b[maxn],c[maxn],cnt;
#define lowbit(x) (x&-x)
int main(){
    ll n,S=0;read(n);
    for(int i=1;i<=n;++i){
        read(a[i]);read(b[i]);
        S^=a[i];a[i]^=b[i];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=cnt;++j){
            if(a[i] & lowbit(c[j])) a[i] ^= c[j];
        }if(a[i] != 0) c[++cnt] = a[i];
    }
    for(int i=1;i<=cnt;++i){
        if(S & lowbit(c[i])) S ^= c[i];
    }
    if(S != 0) puts("1/1");
    else{
        ll x = 1LL<<cnt;
        printf("%lld/%lld
",x-1,x);
    }
    getchar();getchar();
    return 0;
}