矩阵快速幂

Posted on | In |

cot数组一开始是A0，temp数组一开始是A1。我们来模拟下求第13项的斐波那契值是怎么求的。

1
2
3
4
5
第一步:n = 13，执行Matrix(cot,temp)和Matrix(temp,temp)，得到cot数组为A1，t数组为A2，n = 6
第二步:n = 6，执行Matrix(temp,temp)，得到cot数组为A1，t数组为A4，n = 3
第三步:n = 3，执行Matrix(cot,temp)和Matrix(temp,temp)，得到cot数组为A5，t数组为A8，n = 1
第四步:n = 1，执行Matrix(cot,temp)和Matrix(temp,temp)，得到cot数组为A13，t数组为A16，n = 0
退出while循环并输出cot数组对应的值。一共进行了4步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int N = 10000,n;
void Matrix(int (&a)[2][2],int b[2][2]){
    int tmp[2][2] = {0};
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % N;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            a[i][j] = tmp[i][j];
}
int main(){
    while(cin>>n && n!=-1){
        int temp[2][2] = {1, 1, 1, 0},cot[2][2] = {1, 0, 0, 1};
        while(n){
            if(n & 1) Matrix(cot,temp);
            Matrix(temp,temp);

            n /= 2;
        }
        cout<<cot[0][1]<<endl;//!
    }
    return 0;
}

参考链接
https://www.jianshu.com/p/1c3f88f63dec

https://blog.csdn.net/acdreamers/article/details/21822165