洛谷 4159 bzoj 1297 [SCOI2009]迷路 题解

发表于 | 更新于 | 阅读次数：
本文字数： 48 字 | 阅读时长 ≈ 1 分钟

先说一句，矩阵真是太强了，啥玩意都能干。这个题是真的牛逼，做完我仿佛都变成了一个矩阵。

题意简述

给定一个图，，用邻接矩阵给出，每条边的权值是之间的整数（表示边权，表示不连通）。请你求出从到走边权和为的路径数。

思路

拆点。每个点能联通的只有种边权，所以拆成个点，拆成的点之间大的往小的连边，建出来一个的邻接矩阵。
把这个矩阵求快速幂得到次方，位于位置的就是答案了。

具体的思维过程

  1. 如果我们的图边权是，那么该如何做呢？
  2. 如何把我们的图转化成1. 中那个图呢？

    step.1 只有0,1的问题

设矩阵中的位置表示：从到边权和为的情况数。那么应该就等于初始给定的邻接矩阵。

转移方程：枚举中转点，=

然后我们发现，这不就是么（矩阵乘法）。如果还有一点数学基础（或者你没有，但是你对前缀和很熟悉），你会发现，这个式子很容易推出通项

所以，在只有的图中，我们只要把邻接矩阵看成一个数学上的矩阵，拿矩阵快速幂求一下次方即珂。然后位于位置的数就是从到边权和为的方案数了。

step.2 转化

我们发现边权只有种，其中联通的还只有种，所以我们把每个点拆成个点。设表示点拆出来的第个点。为了节省空间，我们令是到中的整数（虽然理论上它应该是到中的整数）。（看到珂别想歪了，我还少一个和一个）。

然后我们还要转换边权。对于同一个，我们令到之间连一条权为的边。对于之间一条边权为的边，那就只要从往之间连一条权为的边即珂。我们发现，经过我们刚刚建的那些辅助边，到之间的间接距离就是，而且我们现在只用了权为和的边。（虽然我说的只有权为的边，但是我没有加上去的边权就是）。

然后现在我们的图由于拆点，就变成了只有和边权的边了。套用刚刚的方法即珂。

具体实现的注意事项

  1. 别忘了膜
  2. 拆点的转化公式：，所以空间复杂度
  3. 开

代码：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define int long long 
	#define mod 2009
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	class Matrix//square matrix
	{
	    #define N 112//changeable
	    private:
	        int a[N][N];
	    public:
	        //variable list
	        int n;//size
	        //initialization
	        Matrix()
	        {
	            memset(a,0,sizeof(a));
	            n=0;
	        }
	        Matrix(int _n)
	        {
	            memset(a,0,sizeof(a));
	            n=_n;
	        }
	        Matrix(int _n,int _x)
	        {_x%=mod;
	            n=_n;
	            for(int i=0;i<N;++i)
	            {
	                for(int j=0;j<N;++j)
	                {
	                    a[i][j]=_x;
	                }
	            }
	        }
	
	        //get value
	        int* operator[](int i)
	        {
	            return *(a+i);
	        }
	
	        //set value
	        void Set(int x)
	        {x%=mod;
	            for(int i=0;i<N;++i)
	            {
	                for(int j=0;j<N;++j)
	                {
	                    a[i][j]=x;
	                }
	            }
	        }
	        void Identity()
	        {
	            memset(a,0,sizeof(a));
	            for(int i=0;i<N;++i)
	            {
	                a[i][i]=1;
	            }
	        }
	        #undef N //112
	};
	Matrix operator*(Matrix x,Matrix y)
	{
	    Matrix ans(x.n,0);
	    int n=ans.n;
	    for(int i=1;i<=n;++i)
	    {
	        for(int j=1;j<=n;++j)
	        {
	            for(int k=1;k<=n;++k)
	            {
	                ans[i][j]+=x[i][k]*y[k][j];
	                ans[i][j]%=mod;
	            }
	        }
	    }
	    return ans;
	}
	Matrix operator^(Matrix x,int p)
	{
	    Matrix ans(x.n,1);
	    ans.Identity();
	    while(p)
	    {
	        if (p&1) ans=ans*x;
	        x=x*x,p>>=1;
	    }
	    return ans;
	}

	int n,t,a[112][112];
	void Input()
	{
		scanf("%lld%lld",&n,&t);
		F(i,1,n) F(j,1,n)
		{
			scanf("%1lld",&a[i][j]);
		}
	}

	Matrix f(91,0);
	int pos(int i,int v)
	{
		return v*n+i;
	}
	void Soviet()
	{
		F(i,1,n) 
		{
			F(j,1,8) f[pos(i,j)][pos(i,j-1)]=1;

			F(j,1,n)
			{
				int x=a[i][j];
				f[i][pos(j,x-1)]=1;
			}
		}

		f=f^t;
		printf("%lld\n",f[1][n]);
	}
	void IsMyWife()
	{
		Input();
		Soviet();
	}
	#undef int //long long 
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}

w