一个人的巴黎

用户名：uq_36478041918

访问量：14986

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：360

奖学金，运用sort函数对结构体类型排序
浏览：283

奖学金，运用sort函数对结构体类型排序
浏览：148

你可能喜欢

A+B for Input-Output Practice (V) （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

矩阵的幂【写个快速幂矩阵】

　　作者: 一个人的巴黎　　　　发表时间：2022-03-28 16:54:13 浏览：192　|　评论：0　

原题链接：矩阵的幂

整数快速幂的求解：[快速幂][快速幂]
矩阵快速幂的不同，在于初始情况乘单位矩阵，而非乘1，并且采用矩阵乘法，而非普通整数乘法
```cpp
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
class M{
public:
    LL data[101][101];
    M()  {
        memset(data,0,sizeof(data));
    }
};

//矩阵乘法
M *Mul(M *m1,M *m2){
    M *ans = new M();
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                ans->data[i][j] += m1->data[i][k] * m2->data[k][j];
            }
        }
    }
    return ans;
}
//用快速幂的方法求矩阵的幂
M *mPow(M *m,int p){
    M *E = new M();
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            if(i == j)  E->data[i][j] = 1;
        }
    }
    while(p!=0){
        if((p&1))
            E = Mul(E,m);
        m = Mul(m,m);
        p>>=1;
    }
    return E;
}

int main()
{
    int n;
    M *res = new M();
    M *a = new M();
    a->data[0][0]=0;
    a->data[0][1]=1;
    a->data[1][0]=2;
    a->data[1][1]=3;
    while(cin>>n){
        res = mPow(a,n);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                cout<<res->data[i][j]<<" ";
            }
        }
        cout<<endl;
        memset(res,0,sizeof(res));
    }
    return 0;
}
```
[快速幂]: https://blog.dotcpp.com/a/84562

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-求函数值（C语言代码）

母牛的故事（C语言代码）

矩阵的幂【写个快速幂矩阵】

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

上车人数（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

数对（C语言代码）

2^k进制数（C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

最好的，

一个人的巴黎

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-求函数值 （C语言代码）

母牛的故事 （C语言代码）

矩阵的幂【写个快速幂矩阵】

评论区

精彩推荐

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

上车人数 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

数对 （C语言代码）

2^k进制数 （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

最好的，

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-求函数值（C语言代码）

母牛的故事（C语言代码）

　　评论区

上车人数（C语言代码）

数对（C语言代码）

2^k进制数（C语言描述，蓝桥杯）