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

Problem - A - Codeforces

題意：
有 N 張卡牌，正面和反面各有一個非負整數。現在兩個人玩遊戲，每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭，進行 Nim 的遊戲。雙方絕頂聰明的前提下，先手贏的機率為何。

制約：
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).

解法：
每張牌有兩種數字這件事情很難處理，所以要先想辦法把它變成一個集合上的問題。
考慮當作是預先取了所有 A[ i ]，然後把 B[ i ] 替代成 A[ i ] ^ B[ i ]。這麼一來，符合原問題的性質，並且問題簡化成了 B 上取子集合，XOR 起來要等於所有 A[ i ] 的 XOR。考慮這個新的集合 B，對於任意一個 B[ i ]，是可以另外找任意一個 B[ j ]，把 B[ i ] 替代成 B[ i ] ^ B[ j ] 的。原因是，考慮取與不取的 2 * 2 種情況，依然是原本的 0, B[ i ], B[ j ], B[ i ] ^ B[ j ]。這提示我們，可以如此隨意進行類似列運算的操作，不改變問題的解。考慮把 B 集合轉換成線性基，由於一行最多不會超過 64 個元素，所以線性基不會超過 64 個，其餘的行都可以被簡化成 0。回到原先的問題，現在要從這些線性基找出一個子集合，使得 XOR 起來是所有 A[ i ] 的 XOR。如果存在方案，基於線性基的性質一定是唯一確定，找一下判斷就可以了。如果確定存在方案，那麼令線性基的數量是 k，從這線性基裡取到那個唯一方案的機率是 2^-k，同時是後手勝利的機率。

時間 / 空間複雜度：
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;
}