HDUOJ 6275 - Mod, Xor and Everything

题面

对于给定的 nn,计算:

(nmod1)(nmod2)[nmod(n1)](n \bmod 1) \oplus (n \bmod 2) \oplus \dots \oplus [n \bmod (n - 1)]

其中 \oplus 表示按位异或。

数据范围

n1012n \le 10^{12}

题目链接

题面链接(L 题)

由于 HDUOJ 卡常丧心病狂,建议读者前往 异或和 - 题目 - LibreOJ 提交(注意输入格式略微存在出入)。

分析

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

对于数 nn,其二进制第 kk 位上的值为:

n2kmod2\left\lfloor \frac{n}{2^k} \right\rfloor \mod 2

那么,对于第 kk 位,经过题目中异或运算后这一位上的答案为:

i=1nnmodi2kmod2\sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \mod 2

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

i=1nnmodi2kmod2=i=1nnnii2kmod2\begin{aligned}
& \sum\limits_{i = 1}^{n} \left\lfloor \frac{n \bmod i}{2^k} \right\rfloor \mod 2 \
= & \sum\limits_{i = 1}^{n} \left\lfloor \frac{n - \left\lfloor \frac{n}{i} \right\rfloor i}{2^k} \right\rfloor \mod 2
\end{aligned}

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

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

对于满足 ni=t\left\lfloor \frac{n}{i} \right\rfloor = t 的某一块,我们记块的最左端为 ll,最右端为 rr,显然有:

nl=nr=t\left\lfloor \frac{n}{l} \right\rfloor = \left\lfloor \frac{n}{r} \right\rfloor = t

以及:

nmodr=nnrr=ntr\begin{aligned}
n \bmod r & = n - \left\lfloor \frac{n}{r} \right\rfloor r \
& = n - tr \
\end{aligned}

那么对于这一块内求和:

i=lrti+n2k=i=rlti+n2k=i=0rlt(ir)+n2k=i=0rlti+(ntr)2k=i=0rlti+(nmodr)2k=f(t,nmodr,2k,rl)\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}

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

复杂度:O(nlogn)\mathcal{O}(\sqrt{n}\log{n})

实现

这道题卡常呜呜呜。

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

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/25/hduoj-6275/