【Caioj1480】矩阵无限方

来源和评测点

Caioj1480

题目

【题目大意】
给定一个n行n列的矩阵A,求出A^x的结果,输出的每个数都mod 10^9+7
【输入格式】
第一行含有两个整数n(1<=n<=10),x(x<=2^31-1)。
接下来n行表示这个矩阵。
【输出格式】
输出结果矩阵,每行n个数之间用一个空格隔开,行尾没有空格,需要回车
【输入样例】
2 3
1 3
5 2
【输出样例】
61 66
110 83

分析

显而易见的裸题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
//*******************全局常量*******************
const ll MOD=1000000007;
//*******************全局定义*******************
struct matrix
{
int row,col;
ll p[20][20];
matrix()
{
memset(p,0,sizeof(p));
}
};
//*******************实现*******************
matrix cheng(matrix a,matrix b)
{
matrix c;
int n=a.row,m=a.col,p=b.col;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c.p[i][j]=(c.p[i][j]+(a.p[i][k]*b.p[k][j])%MOD)%MOD;
c.row=n;c.col=p;
return c;
}
matrix pre(int fn)
{
matrix c;
for(int i=1;i<=fn;i++) c.p[i][i]=1;
c.row=c.col=fn;
return c;
}
matrix power(matrix a,int e)
{
matrix c=pre(a.row);
while(e>0)
{
if(e%2==1) --e,c=cheng(c,a);
//a*c也行,有的博客误导人啊
//因为快速幂中c其实只是好几个a,再多个a罢了
a=cheng(a,a);e/=2;
}
return c;
}
//*******************主函数*******************
int main()
{
int n,x;scanf("%d%d",&n,&x);
matrix s;s.row=s.col=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&s.p[i][j]);
matrix ans=power(s,x);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%lld ",ans.p[i][j]);
printf("\n");
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/bfe0.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%