[C艹]关于"快乘"
查看原帖
[C艹]关于"快乘"
557826
D_guard楼主2022/10/24 17:33

此处“快乘”指类比快速幂,将乘法转化为加法的优化方法。本名应该不叫这个但我忘了...

个人认为通过加法与位运算的结合,该优化方法应该始终有时间效率优势

但本题中使用该优化却拖慢了程序的运行(将快乘用于矩阵乘的运算中)

相关题目: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

这是怎么会逝呢

2022/10/24 17:33
加载中...