题解 P4159 【[SCOI2009]迷路】

我好蒻呀 · 2018-06-09 16:32:17 · 题解

• 首先考虑边权只有 0,1 的情况。
• 令 f_1=给定矩阵
• 因为边权只有 0,1，所以我们可以将这个矩阵的意义转化成：f_t[i][j]=k \Longleftrightarrow i到j的长度为t的路径条数为k。
• 显然对于 f_1 这个意义成立。
• 这样问题就变得简单多了。
• 显然有 f_t[i][j]=\sum\limits_{k=1}^nf_{t-1}[i][k]\times f_1[k][j]。
• 即 f_t=f_{t-1}\times f_1。
• 矩阵乘法满足结合律，故 f_t=f_1^t。
• 于是这种情况下答案就是 f_T[1][n]。
• 再考虑边权 w\in [0,9]\cap\mathbb Z 的情况。
• 因为边权可能大于1，所以给定矩阵不能直接转换成那种含义了。
• 但是我们发现 n\le 10。
• 这意味着我们可以乱搞将每个点都拆开，将这张图转化成边权只有 0,1 的图，这样上面的意义就成立了。
• 经过思考，我们发现可以将每个点拆成 9 个点，令有序数对 (i,j)(i\in [1,n]\cap\mathbb Z,j\in [0,8]\cap\mathbb Z) 表示点 i 拆成的第 j 个点，其中第 0 个点是“真”点，其余的是“假”点。
• 我们可以令 (i,j)(j\in [1,8]\cap\mathbb Z) 表示到“真”点 (i,0) 的距离为 j 的“假”点，只要让 (i,j)(j\in [1,8]\cap\mathbb Z) 向 (i,j-1) 连一条边权为 1 的边。
• 而对于原图中的一条 u\to v 边权为 w 的边，只要让 (u,0) 向 (v,w-1) 连一条边权为 1 的边。
• 这样我们就还原了原图中的边，并且将边权都转化成了 0,1。
• 而每个 (i,j) 又可以唯一对应一个编号 i+j\times n，因此原矩阵就变成了一个 9n\times 9n 的矩阵 f_1。
• 根据前面的推理，同样 f_t=f_1^t。
• 答案就是 f_T[1][n]。
• 假设 m=9n，时间复杂度就是 O(m^3\log T)。

#include <bits/stdc++.h>

const int MaxN = 100; 
const int mod = 2009; 

int n, m, T; 

struct mat
{
    int r, c; 
    int a[MaxN + 1][MaxN + 1]; 

    mat(){}
    mat(const int &_r, const int &_c):
        r(_r), c(_c) 
    {
        memset(a, 0, sizeof(a)); 
    }

    inline void clear()
    {
        memset(a, 0, sizeof(a)); 
        for (int i = 1; i <= r; ++i)
            a[i][i] = 1; 
    }

    inline mat operator * (const mat &rhs) const
    {
        mat res(r, rhs.c); 
        for (int i = 1; i <= r; ++i)
            for (int j = 1; j <= rhs.c; ++j)
            {
                for (int k = 1; k <= c; ++k)
                    res.a[i][j] += a[i][k] * rhs.a[k][j]; 
                res.a[i][j] %= mod; 
            }
        return res; 
    }

    inline mat operator ^ (int p) const
    {
        mat res(r, c), x = *this; 
        res.clear(); 
        for (; p; p >>= 1, x = x * x)
            if (p & 1)
                res = res * x; 
        return res; 
    }
}f; 

inline int pos(const int &u, const int &i)
{
    return u + i * n; 
}

int main()
{
    scanf("%d%d", &n, &T); 
    m = n * 9; 

    f = mat(m, m); 

    int x; 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= 8; ++j)
            f.a[pos(i, j)][pos(i, j - 1)] = 1; 
        for (int j = 1; j <= n; ++j)
        {
            scanf("%1d", &x); 
            if (x)
                f.a[i][pos(j, x - 1)] = 1; 
        }
    }

    f = f ^ T; 
    printf("%d\n", f.a[1][n]); 

    return 0; 
}