题解 P2233 【[HNOI2002]公交车路线】

· · 题解

矩阵乘法吼啊

我们可以构建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的转移路径了

然后我们就很容易得到这样一个代码

#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代码

#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