矩阵快速幂入门

快速幂

整数快速幂

先了解一下整数快速幂.平常我们知道,对于一个x^8次方的运算我们有多种方法:

  1. 直接的八个x相乘
  2. 三个x^2相乘
  3. 两个x^4相乘
    这几种方法的运算效率看得出,第三种是只需要一次乘法,在时间上和计算难度上都优于前两者
    那么如何快速求整数的幂就比较容易了,而且分开的次方数尽量大,且是2的次方数
    可以参见下方代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int QuickPow(int x,int n) //x表示底数 n表示次方
    {
    int res =x;
    int ans =1;
    while(n)
    {
    if(n&1)
    {
    ans*=res;
    }
    res*=res;
    n=n>>1; //二进制从后向前移位 看次方数能否被2整除
    }
    return ans;
    }

现在我们举个例子进行计算
比如x^11
11 的二进制数是 1 0 1 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
初始:

ans = 1; res = x ;

因为最后一位为1,是奇数。所以得到

ans = res * ans = x;
res = res * res = x^2;

接着移位又是1,是奇数(可以想象成没有被整除,把他直接作为一项进行乘)


ans = res * ans = x * (x^2)= x^3;
res = res * res = x^2 * x^2 =x^4;

接着移位为0,,则直接让res平方

res = res * res =x^4 * x^4 = x^8

最后又为1

ans = ans * res = x^3 * x^8
res = res * res = x^8 * x^8 =x^ 16

现在来看看,矩阵快速幂是怎么样的,可以说是将整数幂中的数变成了一个二维矩阵
代码如下

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
struct Matrix //结构体,矩阵类型
{
int m[maxn][maxn];
}ans,res;
//计算矩阵乘法的函数,参数是矩阵a、b和一个n,代表这两个矩阵是几阶方阵
Maxtrix Mul(Maxtrix A,Matrix B,int n)
{
Matrix tmp; //定义一个临时的矩阵,存放A*B的结果
for(int i=1;i<=n;i++)//初始化矩阵
{
for(int j=1;j<=n;j++)
{
tmp.m[i][j]=0;
}
}
for(int i=1;i<=n;i++)//开始计算矩阵
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
tmp.m[i][j]+=A.m[i][k]*B.m[k][j];
}
}
}
return tmp;
}
void QuickPower(int N,int n)//快速幂算法,求矩阵res的N次幂
{
//上面整数的幂的ans初始化为1,而对于矩阵要将其初始化为单位阵
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) ans.m[i][j]=1;
else ans.m[i][j]=0;
}
}
while(N)
{
if(N&1)
{
ans =Mul(ans,res);
}
res=Mul(res,res);
N=N>>1;
}
}

矩阵快速幂典型例题

poj3070 Fibonacci(斐波那切数列)
Fibonacci

Time Limit: 1000MS Memory Limit: 65536K

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
“poj3070”
Given an integer n, your goal is to compute the last 4 digits of Fn

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file
is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

分析

题目的意思就是求第n的斐波那契数为多少,因为f(n) = f(n-1)+f(n-2)得来的,由于题目数据
过大,所以不可能像以前一样通过暴力的方式来解决问题。这里就需要我们用到矩阵快速幂,如图
"power"
则,知道f(n-1)、f(n-2)左乘矩阵,就能得到等号左侧的矩阵,第一个位置即为要求的f(n)
代码如下:

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>  
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>

using namespace std;
#define maxn 3
#define mod int(1e4)
struct Matrix //结构体,矩阵类型
{
int m[maxn][maxn];
}ans,res;
//计算矩阵乘法的函数,参数是矩阵a、b和一个n,代表这两个矩阵是几阶方阵
Matrix Mul(Matrix A,Matrix B,int n)
{
Matrix tmp; //定义一个临时的矩阵,存放A*B的结果
for(int i=1;i<=n;i++)//初始化矩阵
{
for(int j=1;j<=n;j++)
{
tmp.m[i][j]=0;
}
}
for(int i=1;i<=n;i++)//开始计算矩阵
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
tmp.m[i][j]=(tmp.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
}
}
}
return tmp;
}
void QuickPower(int N,int n)//快速幂算法,求矩阵res的N次幂
{
//上面整数的幂的ans初始化为1,而对于矩阵要将其初始化为单位阵
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) ans.m[i][j]=1;
else ans.m[i][j]=0;
}
}
while(N)
{
if(N&1)
{
ans =Mul(ans,res,2);
}
res=Mul(res,res,2);
N=N>>1;
}
}
int main()
{
int N,n;
while(~scanf("%d",&N) && N!=-1)
{
n=2;//二阶方阵
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
res.m[i][j]=1;
}
}
res.m[n][n]=0;
QuickPower(N,n);
printf("%d\n",ans.m[1][2]);
}
}

由于我是从1开始的 所以矩阵至少要开3

本文标题:矩阵快速幂入门

文章作者:ConanMoke

发布时间:2018年08月28日 - 23:08

最后更新:2018年09月06日 - 15:09

原始链接:https://conangentleman.github.io/2018/08/28/Matrix-quick-power/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Donate comment here

-------------本文结束感谢您的阅读-------------