此处“快乘”指类比快速幂,将乘法转化为加法的优化方法。本名应该不叫这个但我忘了...
个人认为通过加法与位运算的结合,该优化方法应该始终有时间效率优势
但本题中使用该优化却拖慢了程序的运行(将快乘用于矩阵乘的运算中)
相关题目:P3390 【模板】矩阵快速幂
我打的快乘:
inline ll qmul(ll x, ll y)
{
if (x > y)
swap(x, y);
ll ot = 0;
while (x)
{
if (x & 1)
ot += y;
x >>= 1;
y <<= 1;
}
return ot % mod;
}
加快乘 用时:3.58s
不加快乘 用时:250ms
这是怎么会逝呢