P3390 【模板】矩阵快速幂

2018-06-27 10:01:27来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

矩阵快速幂

题目描述

给定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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:RMQ算法

下一篇:网络编程:listen函数