主要思路

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

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

主要思路

神仙题。

发现 \(x_1 \oplus x_2 = xorsum\)，所以我们尽量把 \(xorsum\) 的位分给 \(x_2\)。如果 \(xorsum\) 的某位为 \(1\)，那就直接给 \(x_2\) 就好；如果为 \(0\) ，那么有 \(0, 0\) 和 \(1, 1\) 两种情况。所以，我们构造线性基时，通过优先考虑为更高的 \(0\) 的位可以使得答案更大（我们考虑用线性基求最大异或和的过程，优先插入权更大的位置）。

主要思路

我们发现，直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算：划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算，可以考虑 DFS 枚举出每一个点所在的连通块根，然后把连通情况放入线性基中，如果线性基插入失败，那么说明当前的情况不能被表示出，且该状态符合划分，那么计入小答案\(tot\)，最后对答案的贡献就是：\(2^{tot}\)。

现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数，使得\(f(i)\)只被计算一次：

\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]

打表出来就是：

\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]

Continue reading →