主要思路

首先看到这个题可以考虑树套树，然后就做完了。

我们考虑用二维树状数组进行差分。当然，如果按正常的想法差分的话，我们只能想到用前缀和维护单点值，而不是维护区间异或和。我们设差分后的结果：

\[ d_{i, j} = a_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]

主要思路

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

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

A – 神奇的位运算

想了半天，最后一看是离线来维护，直接吐血。

首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和，一种方式是使用主席树进行维护，另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或：我们把每个数往尽可能近的地方塞，这个时候就需要用 map 来判断要不要移动。

Continue reading →

主要思路

这道题还蛮妙的，自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：

• 不存在两个相同的前缀和。
• 不存在一对前缀和，其异或值为\(x\)。

针对\(x\)的大小关系，我们可以分成两种情况：

• \(x \geq 2^n\)，不存在一对\((S_i, S_j)\)的异或为\(x\)，因为存在更高的位并不会被消除。
• \(x < 2^n\)，我们发现每选择一个数作为前缀和，整个\(2^n\)中就会少一个对应的可以被选择的数。所以，我们每次选一个作为\(S_i\)的数时，都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

Continue reading →

D – Numbers of Permutations

思考量很小的一道题。

先用间接法来算。初始答案为\(n!\)，然后考虑容斥掉那些符合排序规则的方案。发现，我们可以分开来考虑，按照容斥的顺序：先考虑只算第一维、第二维的，在加回来两维都考虑的。

第一维和第二维的做法非常显然：排序之后用多重集的排列就行了，考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段，那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。

Continue reading →