shuoj—矩阵幂—矩阵快速幂

2023-12-22 17:32

文章标签 快速矩阵 shuoj

本文主要是介绍shuoj—矩阵幂—矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

矩阵幂

Description

给定1个n阶矩阵A，求它的k次幂Ak。

Input

有多组数据。

每组输入的第一行是2个整数n和k，（n<10，k<10），n表示矩阵的阶。接着是该n阶矩阵A=(aij)n´n的描述，共n行，每行有n个整数，整数之间有一个或多个空格隔开，| aij |<=10。两组数据之间空一行。

Output

对输入的每个n阶矩阵及k，输出k次幂Ak，矩阵行的尾部无空格。

两组输出数据之间空一行。

Sample Input

2 3

0 -4

3 4

1 2 3

4 5 6

7 8 9

Sample Output

8 36

0 -64

7560 9288 11016

17118 21033 24948

26676 32778 38880

解题要求：：1）会求矩阵的乘法运算

解题思路：：通过快速幂的思想，求矩阵的快速幂

要点：：1）如果直接用数组表示矩阵，不能进行乘法运算符的重载，可以通过运用结构实现重载，也可以不用重载。

2）快速幂的了解。

矩阵乘法模板：

void multi(ll d[11][11],ll b[11][11]){memset(c,0,sizeof(c));for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<n;k++){c[i][j]+=d[i][k]*b[k][j];}}}}

c数组定义为全局变量，最后结果保存在c数组中

快速幂模板：

while(N){if(N&1)ret = ret*A;//N换算成2进制后的末尾是否为0N>>1;//N右移一位A = A*A;
}

A^13 = A^8*A^4*A^1用二进制表示A^(1101) = A^(1000)*A^(100)*A^(1)
例如：：N = 13 = 1101（2），N>>1 = 110（2），

具体代码：：

#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;ll a[11][11];
ll ret[11][11];
ll c[11][11];
int m,n;
void multi(ll d[11][11],ll b[11][11]){memset(c,0,sizeof(c));for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<n;k++){c[i][j]+=d[i][k]*b[k][j];}}}
}int main(){int k,ca = 0;while(cin>>n>>k){REP(i,n)REP(j,n)cin>>a[i][j];REP(i,n)REP(j,n)if(i==j)ret[i][j] = 1;else ret[i][j] = 0;//初始化单位矩阵while(k){if(k&1){//ret = ret*a;/**************/multi(ret,a);for(int i=0;i<n;i++){for(int j=0;j<n;j++) {ret[i][j] = c[i][j];}}/***************/}k>>=1;multi(a,a);for(int i=0;i<n;i++){for(int j=0;j<n;j++){a[i][j] = c[i][j];}}}if(ca++ != 0)cout<<endl;REP(i,n){REP(j,n){if(j != 0)cout<<" ";cout<<ret[i][j];}cout<<endl;}}}

其他快速幂题目：点击打开链接

这篇关于shuoj—矩阵幂—矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！