P3390 【模板】矩阵快速幂

attack

发布于 2018-04-13 14:52:26

4930

发布于 2018-04-13 14:52:26

文章被收录于专栏：数据结构与算法数据结构与算法

题目背景

矩阵快速幂

题目描述

给定n*n的矩阵A，求A^k

输入输出格式

输入格式：

第一行，n,k

第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素

输出格式：

输出A^k

共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7

输入输出样例

输入样例#1：

2 1
1 1
1 1

输出样例#1：

1 1
1 1

说明

n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂

裸题！。

注意矩阵相乘的时候tmp的值是累加的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long 
 6 using namespace std;
 7 const int mod = 1e9+7;
 8 LL n,k;
 9 LL a[101][101];
10 LL tmp[101][101];
11 LL ans[101][101];
12 void mul(LL a[][101],LL b[][101])
13 {
14     memset(tmp,0,sizeof(tmp));
15     for(int i=1;i<=n;i++)
16         for(int j=1;j<=n;j++)
17             for(int k=1;k<=n;k++)
18                 tmp[i][j]+=a[i][k]*b[k][j]%mod;
19             
20     for(int i=1;i<=n;i++)
21         for(int j=1;j<=n;j++)
22             a[i][j]=tmp[i][j]%mod; 
23 }
24 void fastpow(LL a[][101],LL k)
25 {
26     
27     for(int i=1;i<=n;i++)ans[i][i]=1;
28     while(k)
29     {
30         if(k%2)mul(ans,a);
31         mul(a,a);
32         k/=2;
33     }
34     for(int i=1;i<=n;i++)
35     {
36         for(int j=1;j<=n;j++)
37             cout<<ans[i][j]%mod<<" ";
38         printf("\n");
39     }
40         
41 }
42 int main()
43 {
44     cin>>n>>k;
45     for(int i=1;i<=n;i++)
46         for(int j=1;j<=n;j++)
47             cin>>a[i][j];
48     fastpow(a,k);
49     return 0;
50 }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-05-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法