自动搬运

查看原文

来自洛谷，原作者为

	我好蒻呀 **

搬运于2025-08-24 21:57:09，当前版本为作者最后更新于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; 
}