给定一个长 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)。