其实矩阵是一个非常有意思的东西呢
矩阵在各个领域都能用到，而且非常方便呢
那么，矩阵长什么样呢
大体长这个样：
$\begin{bmatrix}a_{1,1}&a_{1,2}&a_{1,3}&\cdots\\a_{2,1}&a_{2,2}&a_{2,3}&\cdots\\a_{3,1}&a_{3,2}&a_{3,3}&\cdots\\\vdots&\vdots&\vdots\end{bmatrix}$
当然，矩阵并不一定必须要是方阵
那么，矩阵怎么运算？
其实矩阵的运算也挺简单的：
比如说：
$\begin{bmatrix}10&7\\6&4\end{bmatrix}$ $+$ $\begin{bmatrix}6&1\\8&-3\end{bmatrix}$ $=$ $\begin{bmatrix}16&8\\14&1\end{bmatrix}$
挺好看出来的吧？其实就是每个位置相对应的数相加就行了
减法也跟加法一样
矩阵乘法是跟加减不一样的，而乘法才是矩阵运算的核心
我们同样来看上一个栗子：
$\begin{bmatrix}10&7\\6&4\end{bmatrix}$ $\times$ $\begin{bmatrix}6&1\\8&-3\end{bmatrix}$ $=$
$\begin{bmatrix}116&-11\\68&-6\end{bmatrix}$
是不是跟上面的加减法很不一样呢
我们来仔细看一下这个式子：
$\begin{bmatrix}10&7\\6&4\end{bmatrix}$ $\times$ $\begin{bmatrix}6&1\\8&-3\end{bmatrix}$ $=$
$\begin{bmatrix}10\times6+7\times8&10\times1+7\times-3\\6\times6+4\times8&6\times1+4\times-3\end{bmatrix}$ $=$
$\begin{bmatrix}116&-11\\68&-6\end{bmatrix}$
如果我们设矩阵$A,B,C$且$A\times B=C$,
我们能看出来，矩阵乘法的原理是$A$的横行$\times$$B$的纵行的总和
注：在实际应用中只会应用到矩阵的方阵，所以我们下面提到的矩阵都是方阵
代码实现也很简单（方阵）：1
2
3
4
5
6
7for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c.m[i][j]=c.m[i][j]+a.m[i][k]*b.m[k][j];
}
}
}
我们也可以用数组存矩阵，但是那样用有局限性，这个在后面会提到
矩阵有几个特性，它支持结合律，所以它的乘法运算跟别的乘法运算差不多
说到这里，矩阵到底有什么用呢？
我们来看一下斐波那契数列：
$f(n)=f(n-1)+f(n-2)$
这个式子很简单，只要递推一下就可以了
但是！ 如果我们要求第2000000000项，那么不用说，我们肯定会被卡得怀疑人生
这时候，矩阵就派上用场了
首先，$f_i=f_{i-1}+f_{i-2}=f_{i-1}\times1+f_{i-2}\times1$
而$f_{i-1}=f_{i-1}\times1+f_{i-2}\times1$
$\therefore\begin{bmatrix}f_{i}&0\\f_{i-1}&0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\times\begin{bmatrix}f_{i-1}&0\\f_{i-2}&0\end{bmatrix}$
而$\begin{bmatrix}f_{i-1}&0\\f_{i-2}&0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\times\begin{bmatrix}f_{i-2}&0\\f_{i-3}&0\end{bmatrix}$
即$\begin{bmatrix}f_{i}&0\\f_{i-1}&0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^2\times\begin{bmatrix}f_{i-2}&0\\f_{i-3}&0\end{bmatrix}$
最终，我们能推出$\begin{bmatrix}f_{i}&0\\f_{i-1}&0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{i-2}\times\begin{bmatrix}f_{2}&0\\f_{1}&0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{i-2}\times\begin{bmatrix}1&0\\1&0\end{bmatrix}$
这样的话能比普通的递推式快很多很多很多，因为我们求矩阵快速幂是很快的
那么，矩阵快速幂怎么求？
上面我说过，矩阵满足结合律，所以矩阵快速幂跟普通快速幂几乎一模一样，只是把乘法改成矩阵乘法而已
代码：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
ll n,p;
struct Mat{
ll m[101][101];//存储矩阵的结构体数组
};
Mat a,e;
Mat Mul(Mat x,Mat y){//矩阵乘法
Mat c;
for(int i=1;i<=n;i++){//对于结构体我们不能使用memset
for(int j=1;j<=n;j++){
c.m[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;//核心代码
}
}
}
return c;
}
Mat MatPow(Mat x,ll y){//矩阵快速幂，可以发现除了乘法被换成Mul以外基本跟快速幂没有什么区别
Mat ans=e;
while(y){
if(y&1){
ans=Mul(ans,x);
}
x=Mul(x,x);
y>>=1;
}
return ans;
}
int main(){
scanf("%lld%lld",&n,&p);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&a.m[i][j]);
}
}
for(int i=1;i<=n;i++){//单位矩阵，这个相当于1，对角线都是1，其他的是0，其他矩阵乘以这个矩阵本身的值不变
e.m[i][i]=1;
}
Mat ans=MatPow(a,p);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%lld ",ans.m[i][j]%mod);
}
printf("\n");
}
return 0;
}
从中我们就可以看到开结构体的优越性，而且我们开数组存矩阵的话根本就没办法进行运算
那么，我们的斐波那契数列就可以写出来了：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
int t;
ll n;
struct Mat{
ll m[4][4];
};
Mat a,e;
inline Mat Mul(Mat x,Mat y){
Mat c;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
c.m[i][j]=0;
}
}
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;
}
}
}
return c;
}
Mat Matpow(Mat x,ll y){
Mat ans=e;
while(y){
if(y&1){
ans=Mul(ans,x);
}
x=Mul(x,x);
y>>=1;
}
return ans;
}
Mat aans;
Mat d;
int main(){
e.m[1][1]=1;
e.m[2][2]=1;
//e.m[3][3]=1;
a.m[1][1]=1;
a.m[2][1]=1;
//a.m[3][1]=1;
d.m[1][1]=1;
d.m[2][1]=1;
//d.m[3][2]=1;
d.m[1][2]=1;
//scanf("%d",&t);
scanf("%lld",&n);
if(n<=2){
printf("1\n");
return 0;
}
aans=Mul(Matpow(d,n-2),a);
printf("%lld\n",aans.m[1][1]%mod);
return 0;
}
也就是这道题
那么，如果只这样呢？
$f(1)=f(2)=f(3)=1$
$f(n)=f(n-1)+f(n-3)$
我们可以这么推：
首先，$f_i=f_{i-1}+f_{i-3}=f_{i-1}\times1+f_{i-2}\times0+f_{i-3}\times1$
$f_{i-1}=f_{i-1}\times1+f_{i-2}\times0+f_{i-3}\times1$
$f_{i-2}=f_{i-1}\times0+f_{i-2}\times1+f_{i-3}\times0$
$\therefore\begin{bmatrix}f_{i}&0&0\\f_{i-1}&0&0\\f_{i-2}&0&0\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}\times\begin{bmatrix}f_{i-1}&0&0\\f_{i-2}&0&0\\f_{i-3}&0&0\end{bmatrix}$
而$\begin{bmatrix}f_{i-1}&0&0\\f_{i-2}&0&0\\f_{i-3}&0&0\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}\times\begin{bmatrix}f_{i-2}&0&0\\f_{i-3}&0&0\\f_{i-4}&0&0\end{bmatrix}$
即$\begin{bmatrix}f_{i}&0&0\\f_{i-1}&0&0\\f_{i-2}&0&0\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}^2\times\begin{bmatrix}f_{i-2}&0&0\\f_{i-3}&0&0\\f_{i-4}&0&0\end{bmatrix}$
最终，我们能推出$\begin{bmatrix}f_{i}&0&0\\f_{i-1}&0&0\\f_{i-2}&0&0\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}^{i-3}\times\begin{bmatrix}f_{3}&0&0\\f_{2}&0&0\\f_{1}&0&0\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}^{i-3}\times\begin{bmatrix}1&0&0\\1&0&0\\1&0&0\end{bmatrix}$
所以这样我们就可以得出结果了
代码：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
int t;
int n;
struct Mat{
ll m[4][4];
};
Mat a,e;
inline Mat Mul(Mat x,Mat y){
Mat c;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
c.m[i][j]=0;
}
}
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;
}
}
}
return c;
}
Mat Matpow(Mat x,ll y){
Mat ans=e;
while(y){
if(y&1){
ans=Mul(ans,x);
}
x=Mul(x,x);
y>>=1;
}
return ans;
}
Mat aans;
Mat d;
int main(){
e.m[1][1]=1;
e.m[2][2]=1;
e.m[3][3]=1;
a.m[1][1]=1;
a.m[2][1]=1;
a.m[3][1]=1;
d.m[1][1]=1;
d.m[2][1]=1;
d.m[3][2]=1;
d.m[1][3]=1;
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&n);
if(n<=3){
printf("1\n");
continue;
}
aans=Mul(Matpow(d,n-3),a);
printf("%lld\n",aans.m[1][1]%mod);
}
return 0;
}
也就是这道题
终于讲完啦！