Oct 25, 2018

HDUOJ 6275: Mod, Xor and Everything

题面

对于给定的 \(n\)，计算：

\[ (n \bmod 1) \oplus (n \bmod 2) \oplus \dots \oplus [n \bmod (n - 1)] \]

其中 \(\oplus\) 表示按位异或。

数据范围： \(n \le 10^{12}\)

题面链接：CCPC2018 Hangzhou Problemset（L 题）

提交链接：HDUOJ 6275: Mod, Xor and Everything

由于 HDUOJ 卡常丧心病狂，建议读者前往 LibreOJ 6344: 异或和 提交（注意输入格式略微存在出入）。

分析

对于异或运算，我们不妨依据位运算的位独立性对于其二进制下的每一位逐位考虑。

对于数 \(n\)，其二进制第 \(k\) 位上的值为：

\[ \left\lfloor \frac{n}{2^k} \right\rfloor \pmod 2 \]

那么，对于第 \(k\) 位，经过题目中异或运算后这一位上的答案为：

\[ \sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \pmod 2 \]

我们对其做一点小小的变换：

\[ \begin{aligned} & \sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \pmod 2 \\ = & \sum\limits_{i = 1}^{n} \left\lfloor \frac{n - \left\lfloor \frac{n}{i} \right\rfloor i}{2^k} \right\rfloor \pmod 2 \end{aligned} \]

我们发现这个式子非常类似于类欧几里德可解决的 \(f\) 式子（有一点不一样，但是后文会通过一些变换使其一样）。有关类欧几里德算法的相关内容可参考我的另一篇博客：浅谈类欧几里德算法。

至于 \(\left\lfloor \frac{n}{i} \right\rfloor\)，我们可以对其进行整除分块。

对于满足 \(\left\lfloor \frac{n}{i} \right\rfloor = t\) 的某一块，我们记块的最左端为 \(l\)，最右端为 \(r\)，显然有：

\[ \left\lfloor \frac{n}{l} \right\rfloor = \left\lfloor \frac{n}{r} \right\rfloor = t \]

以及：

\[ \begin{aligned} n \bmod r & = n - \left\lfloor \frac{n}{r} \right\rfloor r \\ & = n - tr \\ \end{aligned} \]

那么对于这一块内求和：

\[ \begin{aligned} \sum\limits_{i = l}^{r} \left\lfloor \frac{-ti + n}{2^k} \right\rfloor = & \sum\limits_{i = -r}^{-l} \left\lfloor \frac{ti + n}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{t(i - r) + n}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{ti + (n - tr)}{2^k} \right\rfloor \\ = & \sum\limits_{i = 0}^{r - l} \left\lfloor \frac{ti + (n \bmod r)}{2^k} \right\rfloor \\ = & f(t, n \bmod r, 2^k, r - l) \end{aligned} \]

简而言之，我们首先通过整除分块得到每一块的 \(l\) 和 \(r\)，并求出这一段中每一位对应的结果，最后将所有段的结果求和并将不同位“组装”起来就是最终答案了。

复杂度：\(\mathcal{O}(\sqrt{n}\log{n})\)。

这道题卡常呜呜呜。

在 \(n\) 比较小的时候，\(\mathcal{O}(n)\) 暴力是比类欧 \(\mathcal{O}(\sqrt{n}\log{n})\) 跑得还要快的…… 故考虑设定一个阈值 \(lim\)，当 \(i\) 不大于 \(lim\) 的时候跑暴力，大于 \(lim\) 的时候跑类欧。对于本弱写的代码，实测得到 \(lim\) 大致取值在 \(2 \times 10^7 \sim 4 \times 10^7\) 范围内时可以在 HDUOJ 上卡进时限。而在 LibreOJ 上这个范围就要宽很多了。

最后附上 我的代码 以供参考。