题解 P4884 【多少个1？】

· · 题解

更好的阅读体验

怎么没人发快速乘的版本啊，那我就来水一发吧，其余思想如BSGS不再赘述。

为什么要快速乘？模数>\sqrt{2^{63}-1}，直接乘会爆long\;long。

正常的快速乘：

LL mul(LL a, LL b, LL P){
    LL ans = 0;
    for(; b; b >>= 1, (a <<= 1) %= P)
        if(b & 1) (ans += a) %= P;
    return ans;
}

这是基于快速幂思想的，所以复杂度为 log，常数爆炸，会愉快地TLE，所以有一篇题解称之为“龟速乘”。

接下来是一份神奇的快速乘:

LL mul(LL a, LL b, LL P){
    LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
    LL R = a * (b & ((1LL << 25) - 1)) % P;
    return (L + R) % P;
}

是不是看起来超级牛逼，一堆位运算。。。

其实看着这么高级其实就是利用了小学生都会的乘法分配律。

我们要计算 a \cdot b\;mod\;p，设 b=L+R。

那么原式就变为为a\cdot(L+R)\;mod\;p=((a\cdot L)\;mod\;p+(a\cdot R)\;mod\;p)\;mod\;p。

我们把 L 钦定为 b 的二进制前 x 位，R 为 b 的后 (64-x) 位。

就得到了以上的代码（以上这份代码 x=25），复杂度近似为O(1)。

用上这样的快速乘就可以AC了。

参考链接：https://zhuanlan.zhihu.com/p/31872064

完整代码及BSGS推导

欢迎大佬来访 (✧◡✧)