矩阵
矩阵的乘法运算
定义
\[A(a_{i,j})_{s\times m}=
\left(
\begin{matrix}
a_{11} & a_{12}&...& a_{1m} \\
a_{21} & a_{22}&...& a_{2m} \\
\vdots & \vdots && \vdots\\
a_{s1} & a_{s2} & \cdots& a_{sm}
\end{matrix}
\right)
B(b_{i,j})_{m\times n}=
\left(
\begin{matrix}
b_{11} & b_{12}&...&b_{1n} \\
b_{21} & b_{22}&...&b_{2n} \\
\vdots&\vdots&&\vdots \\
b_{m1} & b_{m2} & \cdots&b_{mn}
\end{matrix}
\right)\\
\]
\[定义AB=C(c_{i,j})_{s\times n}\\
c_{i,j}=\sum_{k=1}^{m}A(i:k)\times B(k:j)=\sum_{k=1}^{m}a_{i,k}b_{k,j}
\]
代码实现
以n级矩阵为例
通常采用结构体定义矩阵，方便运算
const int N=10010;
struct mat{int w[N][N];
};
mat mat_mul(mat x,mat y){mat res;memset(res.w,0,sizeof(res.w));for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<=n;k++){res.w[i][j]+=x.w[i][k]*y.w[k][j];}}}
}
性质
注意，矩阵乘法无交换律
1.结合律
\[(AB)C=A(BC)
\]
矩阵快速幂
由于矩阵乘法存在结合律
因此便可以采用分治的思想，求一个矩阵的n次方
例题P1962 斐波那契数列
\[F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.
\]
请你求出 \(F_n \bmod 10^9 + 7\) 的值。
构造矩阵
\[\because
\left(
\begin{matrix}
F_n&F_{n-1}
\end{matrix}
\right)
=
\left(
\begin{matrix}
F_{n-1}&F_{n-2}
\end{matrix}
\right)
\left(
\begin{matrix}
1&1\\
1&0
\end{matrix}
\right)\\
\therefore
\left(
\begin{matrix}
F_n&F_{n-1}
\end{matrix}
\right)
=\left(
\begin{matrix}
1&1\\\end{matrix}
\right)\left(
\begin{matrix}
1&1\\
1&0
\end{matrix}
\right)^{n-2}
\]
代码实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
struct mat{ll a[2][2];
};
mat mat_mul(mat x,mat y){mat res;memset(res.a,0,sizeof(res.a));for(int i=0;i<2;i++){for(int j=0;j<2;j++){for(int k=0;k<2;k++){res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;}}}return res;
}
ll mat_pow(ll n){mat res,base;base.a[0][0]=1;base.a[0][1]=1;base.a[1][0]=1;base.a[1][1]=0;memset(res.a,0,sizeof(res.a));res.a[0][0]=1;res.a[0][1]=1;while(n){if(n&1)res=mat_mul(res,base);base=mat_mul(base,base);n>>=1;}return res.a[0][0];
}
ll n;
int main(){scanf("%lld",&n);if(n<=2){printf("1");return 0;}printf("%lld",mat_pow(n-2));return 0;
}
练习
构造转移的矩阵即可
1.P1349 广义斐波那契数列
广义的斐波那契数列是指形如 \(a_n=p\times a_{n-1}+q\times a_{n-2}\) 的数列。
今给定数列的两系数 \(p\) 和 \(q\)，以及数列的最前两项 \(a_1\) 和 $ a_2$，另给出两个整数 \(n\) 和 \(m\)，试求数列的第 \(n\) 项 \(a_n\) 对 \(m\) 取模后的结果。
2.P1939 矩阵加速（数列）
已知一个数列 \(a\)，它满足：
\[a_x=
\begin{cases}1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4
\end{cases}
\]
求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。
3.P3390 【模板】矩阵快速幂
\(给定n\times n 的矩阵A,求A^k\)