「Codeforces 662A」Gambling Nim – 题解

主要思路

考虑设 \(S = \oplus_{i = 1}^n a_i\)，然后将 \(c_i = a_i \oplus b_i\) 扔到线性基里面。我们可以发现，线性基最少数来拼出一个和 \(S\) 一样的数使得局面必输。那么，赢得概率就是 \(1 – (\frac12)^{siz}\)。

当然，如果拼不出来，那么就稳赢了。

代码

// CF662A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200;

typedef long long ll;

int n, bcnt;
ll ai[MAX_N], bi[MAX_N], ci[MAX_N], S, base[200];

bool insert(ll x)
{
	for (int i = 1; i <= bcnt + 1; i++)
		x = min(x, x ^ base[i]);
	if (x > 0)
		base[++bcnt] = x;
	return x > 0;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld%lld", &ai[i], &bi[i]), S ^= ai[i], insert(ai[i] ^ bi[i]);
	if (insert(S))
		puts("1/1");
	else
		printf("%lld/%lld\n", (1LL << bcnt) - 1, 1LL << bcnt);
	return 0;
}