HH去散步
题目背景：
bzoj1875
分析：矩阵快速幂优化DP
这道题有了不能从一条边(x, y)在相邻时刻从x à y，然后y à x，那么本来我想的方式是，定义点对(j, k)上一步是从j à k，那么这一步就只能更新除了从k à j以外的位置，然后发现题目当中有说可能有重边，然后我就想考虑将重边的点重新copy一个，然后就发现这样的复杂度直接就爆掉了······最后发现原来这道题是一道妙妙的用矩乘维护边的转移，我们直接将双向边拆成单项，然后从0标号，那么正向边和反向边的标号x, y就是x = y ^ 1, y = x ^ 1，那么每次转移的时候除了不能用反向边，其他的都可以，直接枚举就可以了。
Source:
/*created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>const int MAXN = 120 + 10;
const int mod = 45989;struct node {int to, id;node(int to = 0, int id = 0) : to(to), id(id) {}
} ;struct edges {int u, v;edges(int u = 0, int v = 0) : u(u), v(v) {}
} e[MAXN];struct matrix {int a[MAXN][MAXN];int n;matrix() {}matrix(int n) : n(n) {for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)a[i][j] = 0;}inline matrix operator * (matrix b) {matrix ans(n);for (int i = 0; i < n; ++i)for (int k = 0; k < n; ++k)for (int j = 0; j < n; ++j)ans.a[i][j] = (ans.a[i][j] + a[i][k] * b.a[k][j]) % mod;return ans;}inline matrix operator ^ (int b) {matrix ans(n), a = *this;for (int i = 0; i < n; ++i) ans.a[i][i] = 1;for (; b; b >>= 1, a = a * a)if (b & 1) ans = ans * a;return ans;}
} map, ans;int method, n, m, step, s, t, x, y, ind;
std::vector<node> edge[MAXN];inline void add_edge(int x, int y) {edge[x].push_back(node(y, ind++));edge[y].push_back(node(x, ind++));
}inline void solve() {scanf("%d%d%d%d%d", &n, &m, &step, &s, &t);for (int i = 0; i < m; ++i) scanf("%d%d", &x, &y), add_edge(x, y), e[i] = edges(x, y);ans = matrix(ind), map = matrix(ind);for (int i = 0; i < m; ++i) {x = e[i].u, y = e[i].v, ind = (i << 1);for (int p = 0; p < edge[y].size(); ++p) {node *e = &edge[y][p];if (e->id != (ind ^ 1)) map.a[ind][e->id] = 1;}x = e[i].v, y = e[i].u, ind = (i << 1 | 1);for (int p = 0; p < edge[y].size(); ++p) {node *e = &edge[y][p];if (e->id != (ind ^ 1)) map.a[ind][e->id] = 1;}}
// for (int i = 0; i < (m << 1); ++i, std::cout << '\n')
// for (int j = 0; j < (m << 1); ++j)
// std::cout << map.a[i][j] << " ";for (int p = 0; p < edge[s].size(); ++p) ans.a[0][edge[s][p].id] = 1;map = (map ^ step - 1), ans = ans * map;for (int p = 0; p < edge[t].size(); ++p) {int id = (edge[t][p].id ^ 1);method = (method + ans.a[0][id]) % mod;}printf("%d", method);
}int main() {solve();return 0;
}