题解 P2233 【[HNOI2002]公交车路线】
ghj1222
2018-09-10 14:39:48
矩阵乘法吼啊
我们可以构建8*8的方阵来代表转移路径
$\begin{pmatrix}0&1&0&0&0&0&0&1\\1&0&1&0&0&0&0&0\\0&1&0&1&0&0&0&0\\0&0&1&0&1&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&0&1\\1&0&0&0&0&0&1&0\end{pmatrix}$
对就是这样的一个方阵
就是主对角线旁边的两个斜线上元素是1，其余元素是0，右上角和左下角还有两个1
代表长度为1的转移路径各有多少
然后呢对他进行N次方就代表长度为N的转移路径了
然后我们就很容易得到这样一个代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define p 1000
struct matrix
{
int a[8][8];
matrix(int option = 0)
{
memset(a, 0, sizeof(a));
if (option == 1)
for (int i = 0; i < 8; i++)
a[i][i] = 1;
if (option == 2)
{
for (int i = 0; i < 7; i++)
a[i][i + 1] = a[i + 1][i] = 1;
a[0][7] = a[7][0] = 1;
}
}
};
matrix operator*(const matrix &x, const matrix &y)
{
matrix ans(0);
for (int k = 0; k < 8; k++)
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
(ans.a[i][j] += x.a[i][k] * y.a[k][j]) %= p;
return ans;
}
matrix qpow(matrix d, int N)
{
matrix ans(1);
while (N > 0)
{
if (N & 1)
ans = ans * d;
d = d * d;
N >>= 1;
}
return ans;
}
int main()
{
int N;
scanf("%d", &N);
printf("%d\n", qpow(matrix(2), N).a[0][4]);
return 0;
}
```
然而这个代码。。。
Input = 6
Output = 12
Wrong Answer
gg了，为啥？
题目中有明确要求，如果Tiger走到公交站E就不会去换车，也就是说E不会有出边，这样我们把矩阵稍作修改
$\begin{pmatrix}0&1&0&0&0&0&0&1\\1&0&1&0&0&0&0&0\\0&1&0&1&0&0&0&0\\0&0&1&0&1&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&0&1\\1&0&0&0&0&0&1&0\end{pmatrix}$
然后就能AC了
AC代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define p 1000
struct matrix
{
int a[8][8];
matrix(int option = 0)
{
memset(a, 0, sizeof(a));
if (option == 1)
for (int i = 0; i < 8; i++)
a[i][i] = 1;
if (option == 2)
{
for (int i = 0; i < 7; i++)
a[i][i + 1] = a[i + 1][i] = 1;
a[0][7] = a[7][0] = 1;
a[4][3] = a[4][5] = 0;
}
}
};
matrix operator*(const matrix &x, const matrix &y)
{
matrix ans(0);
for (int k = 0; k < 8; k++)
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
(ans.a[i][j] += x.a[i][k] * y.a[k][j]) %= p;
return ans;
}
matrix qpow(matrix d, int N)
{
matrix ans(1);
while (N > 0)
{
if (N & 1)
ans = ans * d;
d = d * d;
N >>= 1;
}
return ans;
}
int main()
{
int N;
scanf("%d", &N);
printf("%d\n", qpow(matrix(2), N).a[0][4]);
return 0;
}
```
解释一下为什么邻接矩阵可以做乘法（因为他是矩阵啊）
这里我们规定邻接矩阵中$a[i][j]$表示i->的边数(而非路径长度)
然后呢根据矩阵乘法的定义，$\displaystyle(a*b)[i][j]=\sum_{k=1}^na[i][k]*b[k][j]$根据乘法原理和加法原理，$a[i][k]*b[k][j]$就是由i经过k到j的路径数，那么把k枚举一遍就是i经过j走过两条边的路径数
让我们一起膜拜大佬林瑞堂@[olinr](https://www.luogu.org/space/show?uid=88460)