Luogu P3390 【模板】矩阵快速幂

2018-06-17 22:00:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至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 算法:矩阵快速幂

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 typedef long long ll;
 5 ll x[999][999];
 6 ll ans[999][999];
 7 ll dx[999][999];
 8 const int p=1e9+7;
 9 inline void anscf(int n)
10 {
11     for(int i=1;i<=n;i++)
12      for(int j=1;j<=n;j++)
13       dx[i][j]=ans[i][j],ans[i][j]=0;
14 
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        ans[i][j]=(ans[i][j]+(x[i][k]*dx[k][j])%p)%p;
19 }
20 inline void xcf(int n)
21 {
22     for(int i=1;i<=n;i++)
23      for(int j=1;j<=n;j++)
24       dx[i][j]=x[i][j],x[i][j]=0;
25 
26     for(int i=1;i<=n;i++)
27      for(int j=1;j<=n;j++)
28       for(int k=1;k<=n;k++)
29        x[i][j]=(x[i][j]+(dx[i][k]*dx[k][j])%p)%p;
30 }
31 inline void fastpow(ll n,ll w)
32 {
33     while(w)
34     {
35         if(w%2==1) anscf(n);
36         w/=2;
37         xcf(n);
38     }
39 }
40 int main()
41 {
42     ll n,k;
43     scanf("%lld%lld",&n,&k);
44     for(int i=1;i<=n;i++)
45      for(int j=1;j<=n;j++)
46       scanf("%d",&x[i][j]),ans[i][j]=x[i][j];
47     fastpow(n,k-1);
48     for(int i=1;i<=n;i++)
49     {
50       for(int j=1;j<=n;j++)
51        printf("%lld ",ans[i][j]);
52       puts("");
53     }
54 }

 

标签:

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

上一篇:enote笔记语言(5)——其他(ver0.2)

下一篇:InvalidateRect和UpdateWindow