题解 P3791 【普通数学题】

· · 题解

类似在二进制下数位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前缀和的函数记忆化即可。原因自己思考吧。