题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408
说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?
#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; inline LL read(){ 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(){ n = read(); for (int i=1;i<=n;i++) { a[i] = read(); b[i] = read(); 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; }
楼下是疯子。哈哈
Howdy! This post could not be written any better! Reading through this post reminds me of my old room mate! He always kept chatting about this. I will forward this write-up to him. Fairly certain he will have a good read. Thanks for sharing!
Would love to constantly get updated great site! .