矩阵快速幂

发表于 更新于 分类于 阅读次数： Changyan：

矩阵快速幂

预备知识（矩阵乘法）：http://www.51nod.com/Challenge/Problem.html#problemId=1137

引子：
  • 求斐波那契数列的第n项

思路：借助于矩阵运算和快速幂：

设fn表示斐波那契数列的第n项，我们定义运算矩阵第n项Fn：

和第n+1项：

于是乎，我们可以借助矩阵乘法来寻找二者的关系，于是找到斐波那契的基底矩阵A：

满足以下变换：

因此可以递推得到得到：

问题二：求斐波那契数列的前n项和？我们只需要将原矩阵改一改即可

A矩阵;

有递推公式：

完整代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>

#define N 3

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
#define x first
#define y second 

template <typename T>void read(T &x){x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}x*=f;return;}
template <typename T>void write(T x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');return;}      
//================================= 
LL n;
const int m=1e9+7;
LL a[N][N] = { {0,1,0},
                {1,1,1},
                {0,0,1} };
LL start[3]={1,1,1};

void mul(LL res[],LL start[],LL a[][N]){
    LL temp[N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
            temp[i]=(temp[i]+start[j]*a[j][i])%m;
        }
    memcpy(res,temp,sizeof temp);
}

void multy(LL a[][N],LL b[][N],LL c[][N]){
    LL temp[N][N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                temp[i][j]=(temp[i][j]+(LL)b[i][k]*c[k][j])%m;
            }
        }
    }
    memcpy(a,temp,sizeof temp);
}

//=================================
int main(){
	cin >> n;
	
	for(--n;n;n>>=1){
	    if(n&1) mul(start,start,a);
	    multy(a,a,a);
	}
	
	write(start[1]);
	
	return 0;
}

牛刀小试：

http://newoj.acmclub.cn/problems/2088