首页 > 代码库 > CodeForces - 662A Gambling Nim
CodeForces - 662A Gambling Nim
http://codeforces.com/problemset/problem/662/A
题目大意:
给定n(n <= 500000)张卡片,每张卡片的两个面都写有数字,每个面都有0.5的概率是在正面,各个卡牌独立。
求把所有卡牌来玩Nim游戏,先手必胜的概率。
(⊙o⊙)…由于本人只会在word文档里写公式,所以本博客是图片格式的。
Code
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 template<typename T>inline void read(T &x){ 7 x=0;char ch;bool flag = false; 8 while(ch=getchar(),ch<‘!‘);if(ch == ‘-‘) ch=getchar(),flag = true; 9 while(x=10*x+ch-‘0‘,ch=getchar(),ch>‘!‘);if(flag) x=-x; 10 } 11 inline int cat_max(const int &a,const int &b){return a>b ? a:b;} 12 inline int cat_min(const int &a,const int &b){return a<b ? a:b;} 13 const int maxn = 500010; 14 ll a[maxn],b[maxn],c[maxn],cnt; 15 #define lowbit(x) (x&-x) 16 int main(){ 17 ll n,S=0;read(n); 18 for(int i=1;i<=n;++i){ 19 read(a[i]);read(b[i]); 20 S^=a[i];a[i]^=b[i]; 21 } 22 for(int i=1;i<=n;++i){ 23 for(int j=1;j<=cnt;++j){ 24 if(a[i] & lowbit(c[j])) a[i] ^= c[j]; 25 }if(a[i] != 0) c[++cnt] = a[i]; 26 } 27 for(int i=1;i<=cnt;++i){ 28 if(S & lowbit(c[i])) S ^= c[i]; 29 } 30 if(S != 0) puts("1/1"); 31 else{ 32 ll x = 1LL<<cnt; 33 printf("%lld/%lld\n",x-1,x); 34 } 35 getchar();getchar(); 36 return 0; 37 } 38
CodeForces - 662A Gambling Nim
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。