矩阵乘法
说白了就是
c[i][j] = a[i][k] * b[k][j]
矩阵快速幂
就是把快速幂中整数乘法换成了矩阵乘法
struct ma
{
int m[5][5];
}ans,base;
ma cal(ma a,ma b)
{
ma tmp;
for(int i = 1;i <= 2;i++)
{
for(int j = 1;j <= 2;j++)
{
tmp.m[i][j] = 0;
for(int k = 1;k <= 2;k++) tmp.m[i][j] += a.m[i][k] * b.m[k][j];
}
}
return tmp;
}//矩阵乘法
int qpow(int ci)
{
base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
base.m[1][1] = 0;
ans.m[0][0] = ans.m[1][1] = 1;
ans.m[0][1] = ans.m[1][0] = 0;//初始化矩阵（因题而异）
while(ci)
{
if(ci & 1)
{
ans = cal(ans,base);
}
base = cal(base,base);
ci >>= 1;
}
return ans.m[0][1];
}//快速幂，把整数乘法换成矩阵乘法
或者在结构体中重载运算符
求\(Fibonacci\)数第\(n\)项
用矩阵运算
先写与斐波那契数递推式直接相关：
\[\begin{bmatrix}f_n \\\\ \end{bmatrix}=\begin{bmatrix}1&1\\&\end{bmatrix} \times \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix} \]再补齐左边
\[\begin{bmatrix}f_n \\f_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\&\end{bmatrix} \times \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix} \]补齐矩阵
\[\begin{bmatrix}f_n \\ f_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix} \times \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix} \]再递归下去：
\[\begin{aligned}\begin{bmatrix}f_n \\ f_{n-1}\end{bmatrix}&=\begin{bmatrix}1&1\\1&0\end{bmatrix} \times \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix} \\&= \begin{bmatrix}1&1\\1&0\end{bmatrix} \times \begin{bmatrix}1&1\\1&0\end{bmatrix} \times \begin{bmatrix}f_{n-2} \\ f_{n-3}\end{bmatrix} \\&= \cdots \\&= \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\times \begin{bmatrix}f_{1} \\ f_{0}\end{bmatrix}\end{aligned}\]前面部分使用矩阵快速幂解决
更多肥不拉几
前缀和\(S_n(s_n)\)
由\(s_n = s_{n-1}+f_n\)得
\[\begin{bmatrix}s_n \\\\\\\end{bmatrix}=\begin{bmatrix}1&1&\\\\&\end{bmatrix} \times \begin{bmatrix}s_{n-1}\\f_n\\\\\end{bmatrix} \]右边两者下标差\(1\)，补矩阵
\[\begin{bmatrix}s_n \\f_{n+1}\\\\\end{bmatrix}=\begin{bmatrix}1&1&0\\0 & 1 & 1\\&\end{bmatrix} \times \begin{bmatrix}s_{n-1}\\f_n\\f_{n-1}\\\end{bmatrix} \]再按下标关系搞
\[\begin{bmatrix}s_n \\f_{n+1}\\f_n\end{bmatrix}=\begin{bmatrix}1&1&0\\0 & 1 & 1\\0&1&0\end{bmatrix} \times \begin{bmatrix}s_{n-1}\\f_n\\f_{n-1}\\\end{bmatrix} \]递归
\[\begin{bmatrix}s_n \\f_{n+1}\\f_n\end{bmatrix}=\begin{bmatrix}1&1&0\\0 & 1 & 1\\0&1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}s_{1}\\f_2\\f_{1}\\\end{bmatrix} \]求\(T_n = \sum\limits_{i = 1}^n(if_i)\)
\[\begin{aligned}T_n &= f_1 + 2f_2 + 3f_3 + \cdots + nf_n\\&=nS_n - S_{n-1} - S_{n-2} - \cdots - S_1\\&=nS_n - \sum\limits_{i = 1}^{n-1}S_{i}\end{aligned} \]设\(P_n = \sum\limits_{i = 1}^{n-1}S_{i}\)，则
\[T_n = n \times S_n - P_n \]用矩阵计算\(S_n,p_n\),然后求\(T_n\)
由\(P_n = P_{n - 1} + S_{n-1}\)
\[\begin{bmatrix}P_n \\\\\\\end{bmatrix}=\begin{bmatrix}1&1&&\\\\&\end{bmatrix} \times \begin{bmatrix}P_{n-1}\\S_{n-1}\\\\\end{bmatrix} \]由\(S_n = S_{n-1}+f_n,f_{n+1} = f_n + f_{n-1}\)补
\[\begin{bmatrix}P_n \\S_n\\f_{n+1}\\f_n\end{bmatrix}=\begin{bmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&1&0\end{bmatrix} \times \begin{bmatrix}P_{n-1}\\S_{n-1}\\f_n\\f_{n-1}\end{bmatrix} \]递归
\[\begin{bmatrix}P_n \\S_n\\f_{n+1}\\f_n\end{bmatrix}=\begin{bmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\0&0&1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}P_{1}\\S_{1}\\f_2\\f_{1}\end{bmatrix} \] 标签：begin,end,矩阵,times,bmatrix,快速,乘法 From： https://www.cnblogs.com/MLP123/p/18021993