【bzoj1297】[SCOI2009]迷路 矩阵乘法

题目描述

给出一个 $n$ 个点的有向图，每条边的权值都在 $[1,9]$ 之间。给出 $t$ ，求从 $1$ 到 $n$ ，经过路径边权和恰好为 $t$ 的方案数模2009。

输入

第一行包含两个整数，N T。 接下来有 N 行，每行一个长度为 N 的字符串。 第i行第j列为'0'表示从节点i到节点j没有边。 为'1'到'9'表示从节点i到节点j需要耗费的时间。

输出

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

样例输入

5 30
12045
07105
47805
12024
12345

样例输出

852

---

题解

矩阵乘法

傻题，显然如果没有边权的话就是裸的矩乘。如果有边权的话，拆边的话点数为 $9m$ 的，难以接受。

考虑拆点，将1个点拆成9个连成链，每次将出点对应边权的点连到入点上。这样点数就是 $9n$ 了。

时间复杂度 $O((9n)^3)$

#include <cstdio>

#include <cstring>

char str[15];

int m;

struct data

{

	int v[100][100];

	data() {memset(v , 0 , sizeof(v));}

	int *operator[](int a) {return v[a];}

	data operator*(data &a)

	{

		data ans;

		int i , j , k;

		for(i = 0 ; i < m ; i ++ )

			for(j = 0 ; j < m ; j ++ )

				for(k = 0 ; k < m ; k ++ )

					ans[i][j] = (ans[i][j] + v[i][k] * a[k][j]) % 2009;

		return ans;

	}

}A;

data pow(data x , int y)

{

	data ans;

	int i;

	for(i = 0 ; i < m ; i ++ ) ans[i][i] = 1;

	while(y)

	{

		if(y & 1) ans = ans * x;

		x = x * x , y >>= 1;

	}

	return ans;

}

int main()

{

	int n , k , i , j;

	scanf("%d%d" , &n , &k) , m = n * 9;

	for(i = 0 ; i < n ; i ++ )

	{

		scanf("%s" , str);

		for(j = 0 ; j < 8 ; j ++ ) A[i * 9 + j][i * 9 + j + 1] = 1;

		for(j = 0 ; j < n ; j ++ )

			if(str[j] != '0')

				A[i * 9 + str[j] - '1'][j * 9] = 1;

	}

	printf("%d\n" , pow(A , k)[0][n * 9 - 9]);

	return 0;

}