Bzoj 1875 (矩阵快速幂+图上DP)

BZOJ 1875
题意:求无权无向图中$A$走$k$步到$B$的路径条数。过程中不能走过刚刚走过的边。

没有后面的条件就是模板题了
我们可以先设$dp(i,j)$为走了$i$步到$j$点,而这个没有记录上一条边,就不行了
刚开始想在状态记录前驱点,但是似乎不方便进行转移。。
那么从边的角度来考虑,设$dp(i,j)$为走了$i$步到第$j$条边终点结束,将无向边变成两条有向边。
那么转移$dp(i,j)=\sum dp(i-1,k), k,j$通过某点连接
但是这个DP还是会TLE
这个DP仔细想想可以满足矩阵乘法的要求,那么矩阵快速幂即可。

其实这里可以将边变成一些点。具体是如果一条边可以通过某个节点到另一条边,这两条边在新图中的点连一条边,这条边不能是一条无向边分化的有向边。
那么这里就构造了一个新的图矩阵,这个新图满足了上述条件,在原图中走$k$步相当于在新图中走$k-1$步,那么矩阵快速幂即可。
这个新图矩阵和前面的优化一样,所以是本质一样的算法,一个从 优化 DP 角度,一个从 Floyd 角度

知识点:
1、前向星存图 $en$ 从 $-1$ 开始
2、前向星判合法用 i>=1
3、图上边 DP
4、边转点

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 45989;
const LL MAXN = 125;
LL n, m, t, A, B, en, hd[MAXN];
struct edge {LL u, v, nxt;} ed[MAXN * 2];
struct matrix {
LL a[MAXN][MAXN];
matrix() {ms(a, 0);}
}whw;
void ins(LL u, LL v) {ed[++en] = (edge){u, v, hd[u]}, hd[u] = en;}
matrix mul(matrix a, matrix b) {
matrix ret;
for (LL i = 0; i <= en; ++i)
for (LL j = 0; j <= en; ++j)
for (LL k = 0; k <= en; ++k) ret.a[i][j] = (ret.a[i][j] + (a.a[i][k] * b.a[k][j])) % MO;
return ret;
}
matrix ksm(matrix a, LL b) {
matrix ans, bs = a; int fl = 0;
while (b) {
if (b & 1) {
if (fl) ans = mul(ans, bs); else fl = 1, ans = bs;
}
bs = mul(bs, bs);
b >>= 1;
}
return ans;
}
void clean() {
en = -1, ms(hd, -1);
}
int solve() {
scanf("%lld%lld%lld%lld%lld", &n, &m, &t, &A, &B);
++A, ++B;
clean();
for (LL u, v, i = 1; i <= m; ++i) scanf("%lld%lld", &u, &v), ins(++u, ++v), ins(v, u);
for (LL i = 0; i <= en; ++i)
for (LL j = 0; j <= en; ++j) if (i != j && i != (j ^ 1) && ed[i].v == ed[j].u) whw.a[i][j] = 1;
whw = ksm(whw, t - 1ll);
LL ans = 0ll;
for (LL i = hd[A]; i >= 0; i = ed[i].nxt) {
for (LL j = hd[B]; j >= 0; j = ed[j].nxt) {
ans = (ans + whw.a[i][j ^ 1]) % MO;
}
}
printf("%lld\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------