# CFR 662 A. Gambling Nim ( Linear Basis, Math, Probability )

Problem - A - Codeforces

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of cards in the deck.
Each of the following n lines contains the description of one card, consisting of two integers ai and bi (0 ≤ ai, bi ≤ 1e18).

O( N lg MAXA )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;

int N;
long long A[ MAXN ], B[ MAXN ];

signed main() {
ios::sync_with_stdio( 0 );
cin >> N;
long long S = 0;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ] >> B[ i ];
S ^= A[ i ];
B[ i ] ^= A[ i ];
}
vector< long long > base;
for( int i = 0; i < N; ++i ) {
for( int j = 0; j < base.size(); ++j ) {
if( B[ i ] & ( base[ j ] & -base[ j ] ) ) {
B[ i ] ^= base[ j ];
}
}
if( B[ i ] ) {
base.emplace_back( B[ i ] );
}
}
for( int i = 0; i < base.size(); ++i ) {
if( S & ( base[ i ] & -base[ i ] ) ) {
S ^= base[ i ];
}
}
if( S ) {
cout << "1/1" << endl;
} else {
long long d = 1LL << base.size();
cout << d - 1 << "/" << d << endl;
}
return 0;
}
```