题面：[SCOI2009] 迷路
大秦为你打开题目传送门
题目背景
windy 在有向图中迷路了。
题目描述
该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。
现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？
答案对 $2009$ 取模。
注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
输入格式
第一行包含两个整数，分别代表 $n$ 和 $t$。
第 $2$ 到第 $(n + 1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符，若为 $0$，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$。
输出格式
输出一行一个整数代表答案对 $2009$ 取模的结果。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
1
2
3
4
5
6
| 5 30
12045
07105
47805
12024
12345
|
样例输出 #2
提示
样例输入输出 1 解释
路径为 $1 \to 1 \to 2$。
数据规模与约定
- 对于 $30\%$ 的数据，保证 $n \leq 5$，$t \leq 30$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 10$，$1 \leq t \leq 10^9$。
思路
首先，我们考虑路径只有 01 怎么做，不难想到用类似于 Floyd 的做法写出下面的递推式，设 $dp[t][u][v]$ 表示 $u$ 点和 $v$ 点在 $t$ 时刻到达的路径的方案数。
不难发现，这个递推式非常的相似于矩阵快速幂的计算公式。如果我们把这个 DP 写成矩阵的形式，也就是说我们令每一个 $dp[t]$ 表示 $t$ 时刻任意两点之间的方案数，那么可以得到递推式：
这样就可以用矩阵快速幂求解，这个是路径 01 的做法，那么我们考虑如何把题目转化。由于发现题目给的一个明显性质，每一个边权是 $0\sim 9$ 的数字，我们是不是可以考虑把一条路径拆成若干条长度为 1 的边。这样就可以了。
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int P = 2009;
class Matrix {
public:
int n, m;
vector<vector<ll > > mat;
Matrix(int n, int m) : n(n), m(m), mat(n, vector<ll >(m, 0)) {}
Matrix operator+(const Matrix& B) const {
if(n != B.n || m != B.m) {
return *this;
}
Matrix result(n, m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
result.mat[i][j] = (mat[i][j] + B.mat[i][j]) % P;
}
}
return result;
}
Matrix operator*(const Matrix& B) const {
if(m != B.n) {
return *this;
}
Matrix result(n, B.m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < B.m; ++j) {
result.mat[i][j] = 0;
for(int k = 0; k < m; ++k) {
result.mat[i][j] = (result.mat[i][j] + mat[i][k] * B.mat[k][j] % P) % P;
}
}
}
return result;
}
Matrix power(int p) const {
if(n != m) {
return *this;
}
Matrix result(n, n);
for(int i = 0; i < n; ++i) {
result.mat[i][i] = 1;
}
Matrix base = *this;
while(p > 0) {
if(p % 2 == 1) {
result = result * base;
}
base = base * base;
p /= 2;
}
return result;
}
friend ostream& operator<<(ostream& os, const Matrix& A) {
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < A.m; ++j) {
os << A.mat[i][j] << " ";
}
os << endl;
}
return os;
}
};
int n, m, s;
Matrix mp(0, 0);
int pos(int u, int a) { return u + a * n - 1; }
inline void Input() {
read(n, s);
mp = Matrix(9 * n, 9 * n);
for(int i = 1; i <= n; i++) {
for(int j = 1; j < 9; j++) {
mp.mat[pos(i, j)][pos(i, j - 1)] = 1;
}
}
int w;
for(int u = 1; u <= n; u++) {
for(int v = 1; v <= n; v++) {
scanf("%1d", &w);
if(w != 0) mp.mat[u - 1][pos(v, w - 1)] = 1;
}
}
}
inline void Work() {
printf("%lld\n", mp.power(s).mat[0][n - 1]);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
