P3390矩阵快速幂原题链接

代码由人类编写，解析由AI deepseek-r1:617B书写
建议在博客食用更佳

题目大意

给定一个 $n \times n$ 的矩阵 $A$ 和一个整数 $k$ ，要求计算 $A^k$ 并将每个元素对 $10^9+7$ 取模后输出。

解题思路

矩阵快速幂是解决此类问题的有效方法。其核心思想与普通快速幂类似，通过将指数 $k$ 分解为二进制形式，结合矩阵乘法的结合律，将时间复杂度从 $O(k)$ 优化至 $O(\log k)$ ，每次矩阵乘法的时间复杂度为 $O(n^3)$ ，总时间复杂度为 $O(n^3 \log k)$ 。

具体步骤如下：

初始化单位矩阵：单位矩阵是矩阵乘法的单位元，即 $A^0 = I$ 。
快速幂分解：将指数 $k$ 转换为二进制，逐位处理。若当前二进制位为 1，则将当前基矩阵乘到结果矩阵中。
矩阵乘法：实现矩阵乘法时，需注意取模操作以防止数值溢出。

代码解析

矩阵结构体 Mat：使用二维 vector 存储矩阵元素，并重载乘法运算符 * 实现矩阵乘法。
快速幂函数 mfp：通过二进制分解指数，结合快速幂算法高效计算矩阵幂。
输入输出处理：使用函数 fnn 简化矩阵的输入和输出操作。

复杂度分析

时间复杂度：矩阵乘法复杂度为 $O(n^3)$ ，快速幂过程需要 $O(\log k)$ 次乘法，总时间复杂度为 $O(n^3 \log k)$ 。
空间复杂度：存储矩阵需要 $O(n^2)$ 空间。

注意事项

取模操作：每次矩阵乘法运算后均需对结果取模，避免中间结果溢出。
单位矩阵初始化：当 $k=0$ 时，结果为单位矩阵。
索引处理：矩阵行列索引从 1 开始，便于理解和操作。

示例代码解析

#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>


using ll = int64_t;

const ll p = 1e9+7;
template<class T>
T input(){
    T t;
    std::cin>>t;
    return t;
}
ll n=input<ll>(),k=input<ll>();
void fnn(std::function<void(ll,ll)> func,std::function<void()> f = [](){}){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            func(i,j);
        }
        f();
    }
}
struct Mat{
    std::vector<std::vector<ll>> vec;
    Mat():vec(n+1,std::vector<ll>(n+1,0)){

    }
    Mat&setid(){
        for(ll i=1;i<=n;i++){
            vec[i][i]=1;
        }
        return *this;
    }
    Mat operator*(Mat&that){
        Mat res;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                for(ll k=1;k<=n;k++){
                    res.vec[i][j] = (res.vec[i][j] + vec[i][k]*that.vec[k][j]%p)%p;
                }
            }
        }
        return res;
    }
};


Mat a;
Mat mfp(){
    Mat res;
    res.setid();
    while(k){
        if(k&1)res=res*a;
        a=a*a;
        k/=2;
    }
    return res;
}

int main(){
    fnn([&](ll i,ll j){
        std::cin>>a.vec[i][j];
    });
    const Mat res = mfp();
    fnn([&](ll i,ll j){
        std::cout<<res.vec[i][j]<<' ';
    },[](){
        std::cout<<'\n';
    });
}

关键点解释：