矩阵快速幂取模

发表于 | 更新于 | 阅读次数：

矩阵快速幂，主要用于快速求递推的第n项，时间复杂度可以降低很多。这里有一道裸的矩阵快速幂，可以练习一下矩阵快速幂的写法，同时，也算是记录一下吧。

题目链接

51nod 1113 矩阵快速幂

代码

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
#include <stdio.h>
#include <iostream>
using namespace std;
const long long int maxn = 101, mod = 1000000007;
struct matrix
{
    long long int s[maxn][maxn];
};
long long a, b;
matrix res, ans;
matrix mul(matrix A, matrix B, long long int n)//矩阵乘法，注意矩阵乘法无交换律
{
    matrix C;
    for (long long int i = 1; i <= n; i++)
        for (long long int j = 1; j <= n; j++)
            C.s[i][j] = 0;

    for (long long int i = 1; i <= n; i++)
        for (long long int j = 1; j <= n; j++)
            for (long long int k = 1; k <= n; k++)
                C.s[i][j] += A.s[i][k] * B.s[k][j]%mod;

    return C;
}
void quick(long long int y, long long int n)//快速幂
{

    res = ans;
    while (y)
    {
        if (y & 1)
            ans = mul(ans, res, n);
        res = mul(res, res, n);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                ans.s[i][j] %= mod;
                res.s[i][j] %= mod;
            }
        }
        y = y >> 1;
    }
}

int main()
{
    long long int n, y;
    scanf("%lld%lld", &n, &y);
    --y;
    matrix ans0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> ans.s[i][j];
    quick(y, n);
    //ans0 = mul(ans, ans0, n);
    /* for(int i=1 ;i<3 ;i++)
        {
            for(int j=1 ;j<3 ;j++)
                printf("%lld ",ans0.s[i][j]);
            puts("");
        }*/
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout<< ans.s[i][j]%mod<< ' ';
        puts("");
    }
    return 0;
}
0%