自动搬运

查看原文

来自洛谷，原作者为

	fjzzq2002 **

搬运于2025-08-24 21:52:43，当前版本为作者最后更新于2017-05-30 21:39:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\leq n,m$不方便，不妨将它改为<。

类似在二进制下数位dp，<a的一个限制，我们可以将它拆解为log个“前若干位为abc，后若干位任意”的限制。

我们对于两维都这样拆解，然后$O(log^2n)$进行枚举。

考虑对于i和j的两个这样的限制如何计算∑d(i xor j xor x)。

首先考虑只有i的限制，∑d(i xor x)如何计算，那么我们可以注意到“后若干位任意”的那些位异或完仍然是“后若干位任意”，只要将前面的若干位进行异或，后面若干位仍然任意。

然后注意到例如所有形如010xxxx的d之和可以简单地用0101111和(0100000-1)的前缀和相减得到，所以我们可以直接计算两个d的前缀和，相减即可。

接下来加入了j和j的限制，那么假设i最后a位是任意的，j最后b位是任意的。

不妨设a>=b，那么我们注意到不管j最后b位是啥，只要是任何一个确定的值，异或完i的“任意”的最后a位，仍然是任意的。所以我们只要像上面一样，假设j最后b位是任意一个数，将前若干位异或之后，最后任意的a位直接用前缀和相减。最后乘上$2^b$即可。

d的前缀和可以简单地$O(\sqrt{n})$计算：$\sum_{i=1}^n d(i)=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$，那么这样做就是$O(\sqrt{n}log^2n)$的。

如何去掉一个log呢？只要将计算d前缀和的函数记忆化即可。原因自己思考吧。