CFR 662 A. Gambling Nim ( Linear Basis, Math, Probability )
題意:
有 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; }