img

快速幂

快速幂就是快速算底数的n次幂。你可能疑问，求n次幂算n次叠乘不就行了？当n巨大无比时候，如果需要末尾有效尾数值等信息这个可能超出计算机运算范围。

快速幂时间复杂度为 O(log₂n)， 与朴素的O(n)相比效率有了极大的提高。

采取二进制拆分思想

将一个数字写成二进制的形式进行拆分并利用底数的次方算出。

1
2
3
4
5
6
7
8
9
10
11
12
//非递归快速幂
int qpow(int a, int n)
{
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

快速幂模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//泛型的非递归快速幂
template <typename T>
T qpow(T a, ll n)
{
    T ans = 1; 
    while (n)
    {
        if (n & 1)
            ans = ans * a; 
        n >>= 1;
        a = a * a;
    }
    return ans;
}

矩阵快速幂

斐波那契数列

题目描述

大家都知道，斐波那契数列是满足如下性质的一个数列：

\[F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.\]

请你求出 \(F_n \bmod 10^9 + 7\) 的值。

输入格式

一行一个正整数 \(n\)

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
5

样例输出 #1

1
5

样例 #2

样例输入 #2

1
10

样例输出 #2

1
55

提示

【数据范围】
对于 \(60\%\) 的数据，\(1\le n \le 92\)；
对于 \(100\%\) 的数据，\(1\le n < 2^{63}\)。

观察斐波那契数列的数字和递推式

前几个斐波那契的数列为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

f(n+1) = f(n) + f(n-1)

f(n) = f(n)

则有：

image-20201028195631635

而这个矩阵有很多次幂，就可以使用快速幂

注意这里的Base是需要推理出来的，不是每一道矩阵快速幂都一样的base

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
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
lint m, n;
struct Matrix {
    lint d[2][2];

    Matrix() {
        memset(d, 0, sizeof(d));
    }
//初始化部分
    Matrix operator* (const Matrix& x) {
        Matrix ans;
        for (int i = 0; i <= 1; ++i) {
            for (int j = 0; j <= 1; ++j) {
                for (int k = 0; k <= 1; ++k) {
                    ans.d[i][j] += (d[i][k] * x.d[k][j]) % m;
                }
                ans.d[i][j] = (((ans.d[i][j] % m) + m) % m);
            }
        }
        return ans;
    }
};
//重载乘号部分

Matrix fpow(Matrix a, lint n) {
    Matrix ans;
    ans.d[0][0] = ans.d[1][1] = 1;//初始化
    while (n) {
        if (n & 1) {
            ans = ans * a;
        }
        a = a * a;
        n >>= 1;
    }
    return ans;
}
//快速幂部分

int main() {
    cin >> m >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    } else if (n == 2) {
        cout << 1 << endl;
        return 0;
    }
    //特判部分
    Matrix a;
    a.d[0][0] = 1;
    a.d[0][1] = 1;
    Matrix c;
    c.d[0][0] = 1;
    c.d[0][1] = 1;
    c.d[1][0] = 1;
    //构建Base矩阵部分
    c = fpow(c, n - 2);
    a = a * c;
    cout << a.d[0][0] << endl;
    return 0;
}

【模板】矩阵快速幂

题目背景

一个 \(m \times n\) 的矩阵是一个由 \(m\) 行 \(n\) 列元素排列成的矩形阵列。即形如

\[ A = \begin{bmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \end{bmatrix} \text{.} \]

本题中认为矩阵中的元素 \(a_{i j}\) 是整数。

两个大小分别为 \(m \times n\) 和 \(n \times p\) 的矩阵 \(A, B\) 相乘的结果为一个大小为 \(m \times p\) 的矩阵。将结果矩阵记作 \(C\)，则

\[ c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} \]

而如果 \(A\) 的列数与 \(B\) 的行数不相等，则无法进行乘法。

可以验证，矩阵乘法满足结合律，即 \((A B) C = A (B C)\)。

一个大小为 \(n \times n\) 的矩阵 \(A\) 可以与自身进行乘法，得到的仍是大小为 \(n \times n\) 的矩阵，记作 \(A^2 = A \times A\)。进一步地，还可以递归地定义任意高次方 \(A^k = A \times A^{k - 1}\)，或称 \(A^k = \underbrace{A \times A \times \cdots \times A}_{k \text{ 次}}\)。

特殊地，定义 \(A^0\) 为单位矩阵 \(I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}\)。

题目描述

给定 \(n\times n\) 的矩阵 \(A\)，求 \(A^k\)。

输入格式

第一行两个整数 \(n,k\)。
接下来 \(n\) 行，每行 \(n\) 个整数，第 \(i\) 行的第 \(j\) 的数表示 \(A_{i,j}\)。

输出格式

输出 \(A^k\)

共 \(n\) 行，每行 \(n\) 个数，第 \(i\) 行第 \(j\) 个数表示 \((A^k)_{i,j}\)，每个元素对 \(10^9+7\) 取模。

样例 #1

样例输入 #1

1
2
3
2 1
1 1
1 1

样例输出 #1

1
2
1 1
1 1

提示

【数据范围】

对于 \(100\%\) 的数据，\(1\le n \le 100\)，\(0 \le k \le 10^{12}\)，\(|A_{i,j}| \le 1000\)。

本题只需要构建一个单位矩阵

接下来用输入的矩阵进行快速幂即可

其模板程度比起斐波那契更胜一筹

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
#include<bits/stdc++.h>
#define ll long long
#define gc() getchar()
#define maxn 105
#define mo 1000000007
using namespace std;
int n;
struct ahaha
{
	ll a[maxn][maxn];     
    //一定要用long long存矩阵，否则在过程中会爆掉
	ahaha(){
		memset(a,0,sizeof a);
	}
	inline void build()
    {     
        //建造单位矩阵
		for(int i=1;i<=n;++i)a[i][i]=1;
	}
}a;
ahaha operator *(const ahaha &x,const ahaha &y)
{     
    //重载运算符
	ahaha z;
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mo)%mo;
	return z;
}

ll k;
inline void init()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			cin>>a.a[i][j];
}

int main(){
	init();
	ahaha ans;ans.build();
	do{     
        //递推快速幂，与普通的递推快速幂无异
		if(k&1)ans=ans*a;
		a=a*a;k>>=1;
	}while(k);
	for(int i=1;i<=n;++i)
    {
		for(int j=1;j<=n;++j)
        {
           cout<<ans.a[i][j]<<" ";
        }
        cout<<'\n';
    }
	return 0;
}

练习赛I - Matrix Power Series

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample

Inputcopy Outputcopy
2 2 4 0 1 1 1 1 2 2 3

如果我们构造了我们的递推矩阵为这个

img

取完幂后我们会发现

直接就会出现我们的答案

只需要进行-E即可

img

注意进行快速幂时候矩阵的阶数问题，一定要注意究竟是怎么初始化的

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
#include<bits/stdc++.h>
using namespace std;
const int N=61;
int c[N][N],a[N][N],b[N][N],n,mo;
void mult(int x[N][N],int y[N][N])
{
    int i,j,k;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            {
                c[i][j]=0;
                for (k=1;k<=n;k++) c[i][j]=(c[i][j]+x[i][k]*y[k][j])%mo;
            //乘法
            }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) x[i][j]=c[i][j];
}
int main()
{
    int m,i,j;
    cin>>n>>m>>mo;
    for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++) cin>>a[i][j];
            a[i][i+n]=a[i+n][i+n]=b[i][i]=b[i+n][i+n]=1;
        //一个是单位矩阵，一个是第二象限和第四象限需要乘法
        }
    n*=2;
    //阶数*2
    m++;
    while (m>0)
        {
            if (m%2) mult(b,a);
            m/=2;
            mult(a,a);
        }
    n/=2;
    for (i=1;i<=n;i++) b[i][i+n]--;
    //已经减1
    for (i=1;i<=n;i++)
        {
            for (j=1;j<n;j++) cout<<b[i][j+n]<<" ";
        //输出右边
            cout<<b[i][j+n]<<'\n';
        }
    return 0;
}

矩阵加速（数列）

题目描述

已知一个数列 \(a\)，它满足：

\[ a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} \]

求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。

输入格式

第一行一个整数 \(T\)，表示询问个数。

以下 \(T\) 行，每行一个正整数 \(n\)。

输出格式

每行输出一个非负整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
3
6
8
10

样例输出 #1

1
2
3
4
9
19

提示

  • 对于 \(30\%\) 的数据 \(n \leq 100\)；
  • 对于 \(60\%\) 的数据 \(n \leq2 \times 10^7\)；
  • 对于 \(100\%\) 的数据 \(1 \leq T \leq 100\)，\(1 \leq n \leq 2 \times 10^9\)。

本题也是需要确认base矩阵

此至关重要

1
2
3
4
5
6
7
8
9
10
     F[i]=F[i-1]*1+F[i-2]*0+F[i-3]*1;
 F[i-2]=F[i-1]*0+F[i-2]*1+F[i-3]*0;
F[i-3]=F[i-1]*0+F[i-2]*0+F[i-3]*1;
矩阵：

1 0 1

1 0 0

0 1 0

接下来只需要递推即可。