菜王的 blog

已被严肃卡常，呃呃。你说得对，但是我们有

$\sum_{j = 0}^a \binom bj \equiv \binom{b - 1}a \pmod 2$

考虑证明。首先把左半边改写为 $0 \le j \le a$ 且 $j \subseteq b$ 的 $j$ 个数。那么显然可以把 $a$ 的低位删掉变为 $a'$，使得 $\mathrm{lowbit}(a’) \ge \mathrm{lowbit}(b)$，这不影响答案。

接下来考虑一种计算方式是，枚举 $p$ 使得前面的位上 $a', j$ 相同，第 $p$ 位上 $a'$ 严格比 $j$ 大，然后后面的位任取（或者这样的 $p$ 不存在）。显然当 $p > \mathrm{lowbit}(b)$ 的时候后面任取的方案肯定有偶数种（因为 $j$ 在 $\mathrm{lowbit}(b)$ 这一位上可以取 $0, 1$），这是无意义的，因为我们只关心答案 $\bmod 2$。那么我们只需要考虑 $p = \mathrm{lowbit}(b)$ 与不存在这样的 $p$ 的两种情况，不难发现后者满足则前者一定满足，前者不满足则后者一定满足，此时答案为 $0$；则答案为 $1$ 等价于 $a' \subseteq b - 2^{\mathrm{lowbit}(b)}$，这又等价于 $a \subseteq b - 1$。

下面令 $p$ 为题目中的 $\frac p{100}$。考虑计算一个数被异或的次数。令这个数出现了 $a_0$ 次，其他数分别出现了 $a_1, a_2, \dots, a_k$ 次，可以写出式子：

$\begin{aligned} &\sum_{c = 1}^{\lfloor a_0 p \rfloor} \prod_{i = 1}^k \sum_{j = 0}^c \binom{a_i}j\\ =& \sum_{c = 1}^{\lfloor a_0 p \rfloor} \prod_{i = 1}^k \binom{a_i - 1}c\\ =& \sum_{c = 1}^{\lfloor a_0 p \rfloor} \binom{\cap_{i = 1}^k (a_i - 1)}c\\ =& \binom{\cap_{i = 1}^k (a_i - 1) - 1}{\lfloor a_0 p \rfloor} - 1\\ \end{aligned}$

对于出现次数相等的数，它们的异或次数显然也是相等的，可以合并计算。根据经典结论本质不同的出现次数只有 $\mathcal{O}(\sqrt n)$ 种，于是我们只需要知道所有可能的出现次数，以及对于一个出现次数 $x$，出现次数为 $x$ 的数的个数，以及所有出现次数为 $x$ 的数的异或和就可以暴力算答案了。直接上莫队即可做到单根号。