矩阵快速幂 - azusaaa

归档7

算法3 工程2 竞赛2

355 字

2 分钟

矩阵快速幂

2020-08-15

算法

矩阵

快速幂#

1
int qp(int a, int b) {          //quick_power
2
  int ans = 1;
3
  for (; b; b >>= 1) {
4
    if (b & 1) ans = (long long)ans * a;
5
    a = (long long)a * a;
6
  }
7
  return ans;
8
}

矩阵乘法#

设A为 $m \times p$ 的矩阵，B为 $p \times n$ 的矩阵，那么称 $m \times n$ 的矩阵C为矩阵A与B的乘积，记作 $C = AB$ ，其中矩阵C中的第 $i$ 行第 $j$ 列元素可以表示为： $C_{i,j}=\sum\limits_{k=1}^p a_{i,k} \times b_{j,k}$ 如下所示： $\begin{bmatrix}a&b\\c&d\\e&f\end{bmatrix} \times \begin{bmatrix}g&h&i\\j&k&l\end{bmatrix} = \begin{bmatrix}ag+ch+ei,&aj+ck+el\\bg+dh+fi,&bj+dk+fl\end{bmatrix}$

代码#

1
jz operator*(const jz& x, const jz& y)   //为了方便快速幂采用运算符重载
2
{
3
    jz z;
4
    z.n = x.n;
5
    for (int = 1; i <= z.n; ++i)
6
        for (int j = 1; j <= z.n; ++j)
7
            z.e[i][j] = INF;
8
    for (int k = 1; k <= z.n; ++k)
9
        for (int i = 1; i <= z.n; ++i)
10
            for (int j = 1; j <= z.n; ++j)
11
                    z.e[i][j] += x.e[i][k] + y.e[k][j];
12
    return z;
13
}

所以，矩阵快速幂即为作若干次矩阵乘法，代码如下：

完整代码#

1
#define N 1010
2
struct jz          //矩阵
3
{
4
    short n;
5
    long long e[N][N];
6
} a;
7
jz operator*(const jz& x, const jz& y)
8
{
9
    short i, j, k;
10
    jz z;
11
    z.n = x.n;
12
    for (i = 1; i <= z.n; ++i)
13
        for (j = 1; j <= z.n; ++j)
14
            z.e[i][j] = INF;
15
    for (k = 1; k <= z.n; ++k)
16
        for (i = 1; i <= z.n; ++i)
17
            for (j = 1; j <= z.n; ++j)
18
                if (x.e[i][k] + y.e[k][j] < z.e[i][j])
19
                    z.e[i][j] = x.e[i][k] + y.e[k][j];
20
    return z;
21
}
22
jz qp(jz a, int b) {          //quick_power
23
  jz ans = 1;
24
  for (; b; b >>= 1) {
25
    if (b & 1) ans = (long long)ans * a;
26
    a = (long long)a * a;
27
  }
28
  return ans;
29
}