主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
有趣矩阵技巧
最后更新于 2025-08-28 09:01:30
作者
2huk
分类
算法·理论
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
给定一个长 $n$ 的行向量 $A$ 和 $n \times n$ 的矩阵 $G$。$q$ 次询问给定一个整数 $k$ 求 $A \times G^k$。显然其结果是一个向量。 直接矩阵快速幂能做到 $\mathcal O(n^3q \log k)$。若要求复杂度小于四方呢？ 我们可以预处理 $G^1,G^2,G^4,G^8,\dots$ 等 $G$ 的 $2$ 的幂次方的矩阵。时间复杂度是 $\mathcal O(n^3\log k)$。 对于每次询问，先将 $k$ 二进制分解成 $2^{c_1} + 2^{c_2} + \dots 2^{c_m}$。现在的问题是求解 $A \times G^{2^{c_1}} \times G^{2^{c_2}}\times \dots \times G^{2^{c_m}}$。 向量乘矩阵的复杂度是 $\mathcal O(n^2)$ 的，优于矩阵乘矩阵的 $\mathcal O(n^3)$，而且其结果仍是一个向量。所以我们可以先计算 $A \times G^{2^{c_1}}$，得到向量 $A_1$，再将 $A_1$ 与 $G^{2^{c_2}}$ 相乘得到 $A_2$，以此类推。 单次询问的复杂度是 $\mathcal O(n^2 \log k)$ 的。加上预处理，总复杂度 $\mathcal O((n+q)n^2 \log k)$。
正在渲染内容...
点赞
5
收藏
0
