矩阵加减法
对于矩阵\(A\pm B=C\),直接把每一个位置的两个元素相加或相减。
要求:A 和 B 和 C 行列相同
矩阵乘法
如果 A 是个 \(n\times r\) 的矩阵、 B 是个\(r\times m\)的矩阵,则\(A\times B=C\)是个\(n\times m\)的矩阵(图片来自网络,侵删)
\(C_{i,j}=\sum_{k=1}^r A_{i,k}\bullet B_{k,j}\)
- 不满足交换律\(AB\ne BA\)
- 满足结合律\((AB)C=A(BC)\)
- 满足分配率\(A(B+C)=AB+AC\)
如何加速
例:斐波那契
决策点只有两个,考虑矩阵乘法
构建答案、累乘矩阵
设答案 \(F(n)=\begin{vmatrix} f(n)&f(n-1) \end{vmatrix}\)
需要构建 \(base\) 使得 \(F(n)*base=F(n+1)\)
根据矩阵乘法的运算法则,一列一列的构造
首先 \(F(n+1)=\begin{vmatrix} f(n+1) & f(n) \end{vmatrix}\)
由 \(1*f(n)+1*f(n-1)=f(n+1)\)
得 \(base\) 第一列是 \(\begin{vmatrix} 1 \\ 1 \end{vmatrix}\)
由 \(1*f(n)+0*f(n-1)=f(n)\) 得
得 \(base\) 第二列是 \(\begin{vmatrix} 1 \\ 0 \end{vmatrix}\)
所以\(base=\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}\)
计算结果
\(F(n)=F(2)*base^{n-2}=\begin{vmatrix} f(n)&f(n-1) \end{vmatrix}\)
为什么是 \(F(2)\) :因为 \(F(1)\) 中 \(f(0)\) 无意义
代码实现中,可将 \(F(n)\) 看成 \(2\times 2\) 得矩阵,多余地方补零
\(F(n)=\begin{vmatrix} f(n) & f(n-1) \\ 0 & 0 \end{vmatrix}\)
快速幂初值就是 \(F(2)\) ,然后算。不能算完再乘 \(F(2)\) ,因为矩阵乘法不满足交换律
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
struct mat {
LL a[10][10];
mat() { memset(a,0,sizeof(a)); }
inline mat operator *(mat x) {
mat res;
for(int i=1;i<3;i++)
for(int j=1;j<3;j++)
for(int k=1;k<3;k++)
(res.a[i][j]+=a[i][k]*x.a[k][j])%=mod;
return res;
}
}tmp,res,F;
LL n;
inline void Pow(LL p) {
for(;p;p>>=1,tmp=tmp*tmp)
if(p&1)res=res*tmp;
}
int main() {
scanf("%lld",&n);
if(n<3)return puts("1"),0;
res.a[1][1]=1,res.a[1][2]=1;
res.a[2][1]=0,res.a[2][2]=0;
tmp.a[1][1]=1,tmp.a[1][2]=1;
tmp.a[2][1]=1,tmp.a[2][2]=0;
Pow(n-2);
printf("%lld",res.a[1][1]);
}
例二
设 \(F(n)=\begin{vmatrix} a(n) & a(n-1) & a(n-2) \end{vmatrix}\)
则 \(base=\begin{vmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{vmatrix}\)
然后 \(F(n)=F(3)*base^{n-3}\)
直接求解即可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
const int N=3;
struct mat {
LL a[10][10];
mat() { memset(a,0,sizeof(a)); }
inline mat operator *(mat x) {
mat res;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
for(int k=1;k<=N;k++)
(res.a[i][j]+=a[i][k]*x.a[k][j])%=mod;
return res;
}
}tmp,res;
LL n;
int T;
inline void Pow(LL p) {
for(;p;p>>=1,tmp=tmp*tmp)
if(p&1)res=res*tmp;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%lld",&n);
if(n<4) { puts("1"); continue; }
res.a[1][1]=1,res.a[1][2]=1,res.a[1][3]=1;
res.a[2][1]=0,res.a[2][2]=0,res.a[2][3]=0;
res.a[3][1]=0,res.a[3][2]=0,res.a[3][3]=0;
tmp.a[1][1]=1,tmp.a[1][2]=1,tmp.a[1][3]=0;
tmp.a[2][1]=0,tmp.a[2][2]=0,tmp.a[2][3]=1;
tmp.a[3][1]=1,tmp.a[3][2]=0,tmp.a[3][3]=0;
Pow(n-3);
printf("%lld\n",res.a[1][1]);
}
}
矩阵加维
带常数项 k
如 \(f(n)=f(n-1)+f(n-2)+k\),求 \(f(n)\)
对常数项多加一维,常数得递推式是 \(k_n=k_{n-1}+0\)
\(F(n)=\begin{vmatrix} f(n) & f(n-1) & k_n \end{vmatrix}\)
\(base=\begin{vmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{vmatrix}\)
带未知数 n
如 \(f(n)=f(n-1)+f(n-2)+n\) ,求 \(f(n)\)
未知数递推式 \((n)=(n-1)+1\),
虽然只有三个转移,却需要多一个 1 来辅助 \((n)\) 得转移
\(F(n)=\begin{vmatrix} f(n) & f(n-1) & (n) & 1 \end{vmatrix}\)
\(base=\begin{vmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{vmatrix}\)
求和
如 \(f(n)=f(n-1)+f(n-2)\) ,求 \(S(n)=\sum_{i=1}^n f(i)\)
\(S(n)=S(n-1)+f(n)\)
\(F(n)=\begin{vmatrix} f(n) & f(n-1) & S(n-1) \end{vmatrix}\)
\(base=\begin{vmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{vmatrix}\)
End