BZOJ1297 【SCOI2009】迷路 题解

题目链接：点这里(bzoj)

题目大意

有一个n个节点的有向带权图，给出其邻接矩阵表示法，求0到n-1长度为T的路径个数。

思路

一个性质

若给出一个无权图的邻接矩阵表示法，即若f[i][j]=1表示i,j有连边,f[i][j]=0表示i,j无连边。那么矩阵f^k=f'。f'[i][j]就是i到j经过长度为k的路径个数。
证明：
考虑矩阵乘法的表达式C_{i,j}=\sum_{k=1}^{n}A_{i,k}*B_{k,j}
若矩阵A、B都是该无权图的邻接矩阵表示，那么矩阵乘法中枚举1~n的每一个k，将A_{i,k}*B_{k,j}加进C_{i,j}中的意义，实际上就是枚举一个中介点k，表示i先到k再从k到j，那么这样走的方案数就是i到k的方案数乘上k到j的方案数，也就是A_{i,k}*B_{k,j}。
但是这样仅仅是算出了走一步的方案数，如果要算走k步的方案数，就把k个邻接矩阵乘起来就可以了。因此性质就得证了。

利用性质

本题虽然不满足性质中无权图的特点，但是我们可以通过拆点，把带权图变成无权图。具体方法就是把一个点拆成10个点，然后把i,j长度为k的条件转化一下。直接做快速幂。

代码：

#include <cstdio>
#include <cstring>

const int N = 17, P = 2009;

int n, len, T;
char c;

struct matrix
{
    int arr[N * 10][N * 10];

    matrix operator=(matrix a)
    {
        memcpy(arr, a.arr, sizeof(a.arr));
    }

    matrix operator*(matrix a)
    {
        matrix tmp;
        memset(tmp.arr, 0, sizeof(tmp.arr));
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= len; j++)
                for (int k = 1; k <= len; k++)
                    tmp.arr[i][j] = (tmp.arr[i][j] + arr[i][k] * a.arr[k][j]) % P;
        return tmp;
    }
} a, b;

int main()
{
    memset(a.arr, 0, sizeof(a.arr));
    memset(b.arr, 0, sizeof(b.arr));
    scanf("%d%d", &n, &T);
    len = n * 10 + 10;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            scanf(" %c", &c);
            for (int k = 1; k < c - '0'; k++)
                a.arr[i * 10 + k][i * 10 + k + 1] = 1;
            if (c - '0')
                a.arr[i * 10 + c - '0'][j * 10 + 1] = 1;
        }
    for (int i = 1; i <= len; i++)
        b.arr[i][i] = 1;
    while (T)
    {
        if (T & 1)
            b = b * a;
        a = a * a;
        T >>= 1;
    }
    printf("%d\n", b.arr[11][n * 10 + 1]);
    return 0;
}