“我们的结合，拥有着我们的一部分”
矩阵
矩阵(Matrix)是指一个按照长方阵列排列的集合。一个由 $n$ 行 $m$ 列个数字排列的列表称为“ $m$ 行 $n$ 列”的矩阵，简称 $n*m$ 矩阵，记作：
$\begin{Bmatrix}
a_1&a_2&a_3&…&a_m\\
a_{m+1}&…&…&…&a_{2m}\\
…&…&…&…&…\\
a_{m(n-1)+1}&…&…&…&a_{nm}
\end{Bmatrix}$
矩阵加法/减法
令 $A,B$ 都是 $n*m$ 矩阵，则 $A+B=C$ ，满足：
$C=\begin{Bmatrix}
a_1+b_1&a_2+b_2&a_3+b_3&…&a_m+b_m\\
a_{m+1}+b_{m+1}&…&…&…&a_{2m}+b_{2m}\\
…&…&…&…&…\\
a_{m(n-1)+1}+b_{m(n-1)+1}&…&…&…&a_{nm}+b_{nm}
\end{Bmatrix}$
简单来说，即 $C_{i,j}=A_{i,j}+B_{i,j}$ ，减法同理。
矩阵乘法
$AB=C$ 满足 $C_{i,j}=\sum_{k=1}^{n}{A_{i,k}B_{k,j}}$
矩阵乘法能够实现，仅当 $A$ 的行数与 $B$ 的列数相等时。
举个栗子
$A=\begin{Bmatrix}1&2&3\\1&2&3\\\end{Bmatrix}$ ， $B=\begin{Bmatrix}3&2\\1&3\\2&1\\\end{Bmatrix}$
那么对于 $C=A*B$ ，则
简单来讲就是
$C_{1,1}=\sum_{k=1}^{n=3}{A_{1,k}}*\sum_{k=1}^{m=3}{B_{k,1}}$
那么矩阵乘法的代码实现即是：
1
2
3
4
| for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
c[i][j]+=a[i][k]*b[k][j];
|
矩阵快速幂
对于一个矩阵 $G$ 来说， $G^k$ 中 $G_{i,j}$ 的含义为从 $i$ 走到 $j$ 步数为 $k$ 的方案数。
不用理解太多，就是用矩阵实现快速幂即可，将数乘换成矩阵乘法（蒟蒻改了一下午，才发现把 $i$ 打成了 $j$）
LuoguP3390
AC Code
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
67
68
69
70
71
72
73
74
75
76
77
78
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const ll p=1e9+7;
const int N=101;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
ll n,k;
struct Matrix
{
ll m[N][N];
};
inline Matrix underCalc(Matrix a,Matrix b)
{
Matrix res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int l=1;l<=n;++l)
res.m[i][j]=(res.m[i][j]+(a.m[i][l]*b.m[l][j])%p)%p;
return res;
}
Matrix a;
inline void underExpr()
{
Matrix temp;
memset(temp.m,0,sizeof(temp.m));
for(int i=1;i<=n;++i) temp.m[i][i]=1;
while(k)
{
if(k&1) temp=underCalc(a,temp);
a=underCalc(a,a);
k>>=1;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
printf("%lld ",temp.m[i][j]%p);
printf("\n");
}
}
int main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%lld",&a.m[i][j]);
underExpr();
return 0;
}
|