题解 P3390 【【模板】矩阵快速幂】
MorsLin
2018-03-07 08:48:16
## 矩阵运算法则
- 矩阵 A 的大小为 $n × m$， B 的大小为 $n × k$，设$C = A × B$
则$C_{i,j}=\sum\limits^n_{k=1}A_{i,k}\times B_{k,j}$
例如：
$\begin{bmatrix}2 & 1\\4 & 3\end{bmatrix} \times \begin{bmatrix}1 & 2\\1 & 0\end{bmatrix} = \begin{bmatrix}2 \times 1 + 1 \times 1 & 2 \times 2 + 1 \times 0 \\4 \times 1 + 3 \times 1 & 4\times 2 + 3\times 0 \end{bmatrix} = \begin{bmatrix}3 & 4\\7 & 8\end{bmatrix}$
- 矩阵乘满足结合律：$(AB)C = A(BC)$
- 有一种特殊的矩阵：单位矩阵，它从左上角到右下角的对角线上的元素均为1，其他元素均为0。它在矩阵乘中相当于数乘中的1，即任何矩阵乘它都等于本身。
例：
$e = \begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$
以上这些就是学会矩阵快速幂前必备的基础知识。
## 代码实现
- 理解了矩阵乘法之后，我们可以用函数来模拟矩阵乘。
```cpp
Mat Mul(Mat x, Mat y) //矩阵乘
{
Mat c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c.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++)
c.m[i][j] = (c.m[i][j] + x.m[i][k] * y.m[k][j] % mod) % mod;
return c;
}
```
- 因为矩阵乘满足结合律，所以快速幂完全适用于矩阵，矩阵快速幂和普通快速幂几乎一模一样，不同点在于乘号改成了 Mul 函数（不会普通快速幂的请前往[P1226](https://www.luogu.org/problemnew/show/P1226)）
```cpp
Mat pow(Mat x, LL y) //矩阵快速幂
{
Mat ans = e;
while (y)
{
if (y & 1)
ans = Mul(ans, x);
x = Mul(x, x);
y >>= 1;
}
return ans;
}
```
知道这些知识后，这道题基本就可以 AC 了。要注意开 long long，不然会爆零。
AC代码：
```cpp
#include <iostream>
#include <cstring>
#define mod 1000000007
#define LL long long
using namespace std;
struct Mat
{
LL m[101][101];
}; //结构体存矩阵
Mat a, e; //a是输入的矩阵，e是单位矩阵
LL n, p;
Mat Mul(Mat x, Mat y) //矩阵乘
{
Mat c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c.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++)
c.m[i][j] = (c.m[i][j] + x.m[i][k] * y.m[k][j] % mod) % mod;
return c;
}
Mat pow(Mat x, LL y) //矩阵快速幂
{
Mat ans = e;
while (y)
{
if (y & 1)
ans = Mul(ans, x);
x = Mul(x, x);
y >>= 1;
}
return ans;
}
int main()
{
//输入
cin >> n >> p;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a.m[i][j];
//算法核心
for (int i = 1; i <= n; i++)
e.m[i][i] = 1;
Mat ans = pow(a, p);
//输出
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << ans.m[i][j] % mod << " ";
cout << endl;
}
return 0;
}
```
P.S. 关于用结构体的好处：向函数中传参和变量之间赋值比较方便。直接用二维数组当然也没什么问题