首页 > 其他 > 详细

矩阵快速幂

时间:2017-09-18 09:22:40      阅读:207      评论:0      收藏:0      [点我收藏+]

应该还蛮好理解的。。

 1 #include <cstdio>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 const LL maxn=105, prime=1e9+7;
 6 LL n, k, mat[maxn][maxn];
 7 LL ans[maxn][maxn], tmp[maxn][maxn], tmp2[maxn][maxn];
 8 
 9 void plus(LL a[maxn][maxn], LL b[maxn][maxn]){
10     for (LL i=0; i<n; ++i) for (LL j=0; j<n; ++j){
11         tmp2[i][j]=0;
12         for (LL k=0; k<n; ++k)
13             tmp2[i][j]=(tmp2[i][j]+(a[i][k]*b[k][j])%prime)%prime;
14     }
15     for (LL i=0; i<n; ++i) for (LL j=0; j<n; ++j)
16         a[i][j]=tmp2[i][j];
17 }
18 
19 int main(){
20     scanf("%lld%lld", &n, &k);
21     for (LL i=0; i<n; ++i) for (LL j=0; j<n; ++j)
22         scanf("%lld", &mat[i][j]), tmp[i][j]=mat[i][j];
23     for (LL i=0; i<n; ++i) for (LL j=0; j<n; ++j)
24         if (i==j) ans[i][j]=1;
25     while (k){
26         if (k&1) plus(ans, tmp);
27         plus(tmp, tmp);
28         k>>=1;
29     }
30     for (LL i=0; i<n; ++i){
31         for (LL j=0; j<n; ++j)
32             printf("%lld ", ans[i][j]);
33         printf("\n");
34     }
35     return 0;
36 }

 

矩阵快速幂

原文:http://www.cnblogs.com/MyNameIsPc/p/7541318.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!