快速幂杂谈

总觉得快速幂挺深刻的

观前提示

作者很菜, 只是一个普通的中学生

难免有不严谨的地方, 轻喷

普通快速幂

i64 ksm (i64 a, i64 b, i64 mod) {
    i64 res = 1;
    i64 base = a % mod;

    while (b) {
        if (b & 1) { (res *= base) %= mod; }
        (base *= base) %= mod;
        b >>= 1;
    }    

    return res;
}

这是一个非常朴素的快速幂

记 表示 二进制下的第 位

由于

又因为存在递推式

所以她可以在 的时间复杂度内, 求出

但快速幂真的只能求 吗?

那也没必要写这篇文章了对不对

(广义) 快速幂

事实上, 任何幺半群上的运算的幂都可以使用快速幂计算。

形式化地, 我们定义某幺半群上有运算

根据定义, 这个幺半群上存在单位元

并且由于 具有结合律, 可以被拆分成长度为 的幂次的几组, 再合并即可

但这还只是抽象代数层面的解释。

具体地, 除了乘法, 还有什么样的运算具有结合律呢?

加法

显然 和加法构成幺半群, 满足以上所的性质

这便是我们常说的龟速乘

应用

应用并不十分广泛, 主要用于带模乘法会爆 long long 的时候

矩阵乘法

根据 感性理解 线性代数知识, 我们知道矩阵乘法具有结合律

应用

定长路径计数

给定一个 个点的有向图 / 无向图, 求某两点间长度为 的路径数量

这类题目有非常鲜明的特征,

一般来说 不会特别大 (毕竟矩阵乘法是 的),

但是 会开的特别大 (比如开到 )

做法并不困难

设邻接矩阵为 , 则 的长为 的路径数量为

容易考虑一个 dp 来证明这个做法的正确性

定长最短路

求解 恰好经过经过 的边的最短路的长度

首先引入广义矩阵乘法

我们有两个二元运算

那么对于矩阵 有

我们对邻接矩阵 求 矩阵乘法的 次幂

则 即为 恰好经过 条边的最短路长度

好像这个做法还有一个名字是倍增 floyd

加速递推

这个算是非常常见了

感性的来说，矩阵快速幂可以加速 简单重复 的递推

所以在看到严重的数量级不平衡时（如 且暴力转移复杂度为 或 的时候），可以考虑构造大小为 的转移矩阵来加速转移

卷积

首先给出两个向量的 卷积的定义

对于两个向量 和 , 她们的 卷积

卷积也是具有结合律的

应用

她可以优化 dp