矩阵快速幂+斐波那契
一、矩阵乘法
矩阵乘法也就是AXB=A第I
行分别与B的第J
列的对应元素依次相乘:
那么斐波那契怎么用举证计算呢,我们知道斐波那契数列是:
\[\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;
}