662A，戳我戳我

Solution:

• 我们先取\(ans=a[1] \bigoplus a[2] \bigoplus ... \bigoplus a[n]\)，然后我们定义\(c[i]=a[i] \bigoplus b[i]\)，我们就可以知道每异或一个\(c[i]\)，就是更换选取\(a[i],b[i]\)，这里很好想。
• 然后我们要处理出\(c[i]\)，中有多少子集异或和为\(ans\)，这样异或出来总和为\(0\)，这个我们就可以用线性基了。
• 然后后面求子集我还是没有太弄懂，看了题解也有点蒙，先留一个坑
• 题解

Code:

//It is coded by Ning_Mew on 5.31

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn=5e5+7;

int n,tot=0;

LL a[maxn],b[maxn],c[maxn],x[maxn],ans=0;

bool push(LL s){

  for(int i=63;i>=0;i--){

    if((s>>i)&1){

      if(x[i]){s=s^x[i];}

      else {x[i]=s;return true;}

    }

  }return false;

}

LL q_pow(LL xx,LL t){

  LL re=1;

  while(t){

    if(t%2){re=re*xx;}

    xx=xx*xx;t=t/2;

  }return re;

}

int main(){

  scanf("%d",&n);

  for(int i=1;i<=n;i++){

    scanf("%I64d%I64d",&a[i],&b[i]);

    c[i]=a[i]^b[i];ans^=a[i];

  }

  for(int i=1;i<=n;i++){

    if(push(c[i]))tot++;

  }

  if(push(ans)){printf("1/1\n");return 0;}

  else{

    printf("%I64d/%I64d\n",q_pow(2,tot)-1,q_pow(2,tot));

  }

  return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会终生找不到妹子！！！