为什么要写这种不值得一提的东西
因为我太弱了
从最简单的斐波那契数列开始
第一步 确定递推
我们肯定是要先找到递推公式的，比如这个就是\(f[i]=f[i-1]+f[i-2]\)
第二步，写出当前矩阵和目标矩阵
采用宋氏矩阵分析法，我们写出所有的元素:
\[\begin{bmatrix} f[i-1]\\ f[i-2]\\ \end{bmatrix} \rightarrow (我们把每一个可以递推的元素下标+1得到目标) \begin{bmatrix} f[i]\\ f[i-1]\\ \end{bmatrix} \]第三步 确定转移矩阵的长宽
值得肯定的是，我们要构造的矩阵肯定是\(2\times 2\)的，毫无疑问
第四步 将转移矩阵中的一行拿出来与现有矩阵按位对比
对于没有出现在原始矩阵内的项（第一行）
我们一定是要利用到递推公式的，那么转移矩阵的系数一定与递推系数对应：\(1,1\)
对于原本就有的项（其他行）
我们通过操作\(0,1\)的存在就可以直接得到
实操
对于斐波那契数列数列写出的转移矩阵如下
\[\begin{bmatrix} 1&1\\ 1&0\\ \end{bmatrix} \]你已经很好的掌握了构造矩阵了，再做一点基础巩固练吧！
求\(f_n=a\times f_{n-1}+b\times f_{n-2}+c\times f_{n-3}+d\)的转移矩阵
掌握了这个应该差不多能做大多数不太难的矩阵加速了
首先按照我们分析的步骤来，已经有递推了，那我们就先写出所有元素
\[\begin{bmatrix} f_{n-1}\\ f_{n-2}\\ f_{n-3}\\ d\\ \end{bmatrix} \rightarrow \begin{bmatrix} f_{n}\\ f_{n-1}\\ f_{n-2}\\ d\\ \end{bmatrix} \]然后我们写出的转移矩阵肯定是\(4\times 4\)的对吧
最后再逐行分析
第一行显而易见：\([a,b,c,1]\)
后面的也比较容易了，最后得到的就是这个:
\[\begin{bmatrix} a&b&c&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ \end{bmatrix} \]最后再来一点矩阵快速幂就好了，记得一定要初始化矩阵哦，这里为了练习一下，就手写一下代码，出锅了不要骂呜呜呜
点击查看代码
struct Matrix{int n,m,a[maxn][maxn];Matrix(){memset(a,0,sizeof a);};}
Matrix operator*(Matrix a.Matrix b)
{
Matrix tmp;tmp.n=a.n,tmp.m=b.m;
for(int i=1;i<=a.n;i++)
{
for(int j=1;j<=b.m;j++)
{
int c=0;
for(int k=1;k<=a.m;k++)c+=a.a[i][k]*b.a[k][j];
tmp.a[i][j]=c;
}
}
return tmp;
}
Matrix base(int n)
{
Matrix tmp;tmp.n=tmp.m=n;
for(int i-1;i<=n;i++)tmp.a[i][i]=1;
return tmp;
}
Matrix Mpower(Matrix a,int b)
{
Matrix ans=base(a.n);
while(b)
{
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}