「SCOI2009」迷路

发表于 | 分类于 | | 浏览量： 次

原来是矩乘！

传送门

洛谷P4159

BZOJ1297

题解

先来考虑如果边权全都为$1$怎么处理。

设$G[i][j][k]$表示从$i$走到$j$，步数恰好为$k$的方案数。

不难推出转移方程：

而这正是一个矩阵乘法的式子。

令转移矩阵为$F$，其中$F[i][j]$表示从$i$一步走到$j$的方案数。如果$i,j$之间有边则$F[i][j]=1$，否则$F[i][j]=0$。

所以有答案矩阵$G_T=F^T$，矩阵快速幂即可。

还有就是由于原题中边权不一定为$1$，但是小于等于$9$。

所以可以暴力拆点，把每个点拆成$9$个点，然后就可以把所有边的边权转化为$1$了。

时间复杂度$O((9n)^3\log T)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100,TT=2009;
int n,T;
int GetC()
{
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	return ch-'0';
}
struct Matrix
{
	int n,m,a[maxn][maxn];
	Matrix(){n=m=0;memset(a,0,sizeof(a));}
	Matrix operator * (const Matrix& b)
	{
		Matrix c;
		c.n=n;c.m=b.m;
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				for(int k=1;k<=m;k++)
					c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%TT;
		return c;
	}
}F,G;
Matrix QP(Matrix a,int b)
{
	Matrix ret=a,w=a;b--;
	while(b)
	{
		if(b&1) ret=ret*w;
		w=w*w;b>>=1;
	}
	return ret;
}
int main()
{
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int C=GetC();
			if(C!=0) F.a[(i-1)*9+1][(j-1)*9+C]=1;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<9;j++)
			F.a[(i-1)*9+j+1][(i-1)*9+j]=1;
	F.n=F.m=n*9;
	G=QP(F,T);
	printf("%d\n",G.a[1][(n-1)*9+1]);
	return 0;
}