快速幂

第一次遇到快速幂是在做杭电题HDU2034 人见人爱A^B，求A^B的最后三位数表示的整数。看到题目的第一反应是用高精度来求，最后去后三位，反正高精度写的非常熟练了，几十行代码写完之后发现本题数据其实并不大，是一道水题而已，于是写了个很水的循环取余，后来就在评论区知道了快速幂这么个快速算法。

1
2
3
4
5
6
7
8
9
10
typedef long long ll;  
ll mod_pow(ll x, ll n, ll mod){  
	ll res = 1;  
	while( n > 0 ){   
		if( n & 1 ) res = res * x % mod;    //n&1 即 n%2  
		x = x * x % mod;  
		n >>= 1;                 //n >>= 1 即 n/=2  
	}  
	return res;  
}

​

矩阵快速幂

刷北邮复试机考题遇到了一道板子题，直接套上就可以了，顺便总结一下这个知识点。

给定一个n*n的矩阵，求该矩阵的k次幂，即P^k。

AC代码：

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int MAXN = 15;
const int MOD = 1e8;

struct node
{
    int mat[MAXN][MAXN]; //矩阵
    int row, col;
    void init(){ //初始化為單位矩陣
        memset(mat, 0, sizeof(mat));
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                mat[i][j] = (i==j);
            }
        }
    }
};

node mod_mul(node a, node b, int p) //矩阵乘法
{
    node ans;
    ans.row = a.row;
    ans.col = b.col;
    memset(ans.mat, 0, sizeof(ans.mat));
    for (int i = 0; i < ans.row; i++)
        for (int j = 0; j < ans.col; j++)
            for (int k = 0; k < a.col; k++)
            {
                ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
                ans.mat[i][j] %= p;
            }
    return ans;
}

node mod_pow(node a, int k, int p) //矩陣快速冪
{
    node ans;
    ans.row = a.row;
    ans.col = a.col;
    ans.init();
    while (k){
        if (k & 1) 
            ans = mod_mul(ans, a, p);
        a = mod_mul(a, a, p);
        k >>= 1;
    }
    return ans;
}

int main()
{
    node m;
    int n, k;
    while (scanf("%d%d", &n, &k)!=EOF)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++){
                scanf("%d", &m.mat[i][j]);
                m.mat[i][j] %= MOD;
            }  
        m.col = m.row = n;
        node ans = mod_pow(m, k, MOD);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (j != 0)
                    printf(" ");
                printf("%d", ans.mat[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}