「Codeforces 662A」Gambling Nim – 题解

主要思路

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

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

继续阅读「Codeforces 662A」Gambling Nim – 题解

AtCoder Grand Contest 045 – 解题报告

A – Xor Battle

感觉有点傻逼啊。

对于 0 而言,我们只需要最后的答案为 0 即可。那么,我们从后往前进行维护,维护 \(0\) 位置上权值组合而成的线性基,然后每次到 \(1\) 位置的时候就在里面查即可,如果没查到,那么对于 \(1\) 而言,后面的 \(0\) 并不足以抵消该操作,所以可以判 \(1\) 获胜,亦而反之。

继续阅读AtCoder Grand Contest 045 – 解题报告

「LibreOJ」#6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set – 题解

主要思路

神仙题。

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

继续阅读「LibreOJ」#6060「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set – 题解

BZOJ 4671:异或图题解

主要思路

我们发现,直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算:划分至少\(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)! \]

继续阅读BZOJ 4671:异或图题解