点击刷新
矩阵快速幂+斐波那契
一、矩阵乘法
矩阵乘法也就是AXB=A第I行分别与B的第J列的对应元素依次相乘：
\[\begin{bmatrix}
a&c\\
b&d
\end{bmatrix}
\times
\begin{bmatrix}
e&g\\
f&h
\end{bmatrix}
=
\begin{bmatrix}
a\times e+c\times f&a\times g+c\times h\\
b\times e+d\times f&b\times g+d\times h
\end{bmatrix}
\]
那么斐波那契怎么用举证计算呢，我们知道斐波那契数列是：
\[\begin{bmatrix}
f(1)&f(2)\\
f(3)&f(4)
\end{bmatrix}
\times
\begin{bmatrix}
0&1\\
1&1
\end{bmatrix}
=
\begin{bmatrix}
f(2)&f(1)+f(2)\\
f(4)&f(3)+f(4)
\end{bmatrix}
=
\begin{bmatrix}
f(2)&f(3)\\
f(4)&f(5)
\end{bmatrix}
\]
那么我们假设：
\[A=
\begin{bmatrix}
f(1)&f(2)\\
f(3)&f(4)
\end{bmatrix}
B=
\begin{bmatrix}
0&1\\
1&1
\end{bmatrix}
\]
那么：
\[A\times B^n=
\begin{bmatrix}
f(n+1)&f(n+2)\\
f(n+3)&f(n+4)
\end{bmatrix}
\]
所以当要求取的斐波那契的数量特别大的时候，我们就需要将$$B^n$$快速的算出来，那么这个时候就会联想到快速幂，但是我们是矩阵，所以只需要把矩阵乘法的方法加到快速幂当中就能够解决问题了。
快速幂：
long long qpow(long long a,long long b){
while(a){
long long ans=0;
if(a&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b=b>>1;
}
return ans;
}
矩阵乘法
原文(板子)链接：https://blog.csdn.net/lzyws739307453/article/details/90144987
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵b，n为矩阵的大小
Mat c;//临时矩阵c
memset(c.m, 0, sizeof(c.m));
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] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
return c;
}
矩阵快速幂：
struct Mat {
ll m[MAXN][MAXN];
}ans, a;//ans为结果矩阵，a为输入矩阵
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵b，n为矩阵的大小
Mat c;//临时矩阵c
memset(c.m, 0, sizeof(c.m));
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] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
return c;
}
Mat _power(Mat a, int b, int n) {//计算a^b，n为矩阵的大小
for (int i = 1; i <= n; i++)//构造单位矩阵
ans[i][i] = 1;
while (b) {
if (b & 1)
ans = Mul(ans, a, n);
a = Mul(a, a, n);
b >>= 1;
}
return ans;
}
© 著作权归作者所有
举报
发表评论
0/200
