laekov

乍一看矩阵水题，然后发现不能走回头路。

于是改一下把边当做点，把点当作转移，转移的时候就可以避免走过去就走回来的情况了。

说好的复习会考呢？

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define _l (long long int)

const int mod = 45989;

const int maxn = 123;

class matrix {

public:

int n, a[maxn][maxn];

inline matrix() {

}

inline matrix(int n0, bool one = 0) {

n = n0;

memset(a, 0, sizeof(a));

if (one)

for (int i = 0; i < n; ++ i)

a[i][i] = 1;

}

void operator =(const matrix& x) {

n = x. n;

for (int i = 0; i < n; ++ i)

for (int j = 0; j < n; ++ j)

a[i][j] = x. a[i][j];

}

matrix operator *(const matrix& x) {

matrix r(n);

for (int k = 0; k < n; ++ k)

for (int i = 0; i < n; ++ i)

for (int j = 0; j < n; ++ j)

r. a[i][j] = (r. a[i][j] + _l a[i][k] * x. a[k][j] % mod) % mod;

return r;

}

};

struct edge {

int a, b;

inline edge(int a0 = 0, int b0 = 0) {

a = a0, b = b0;

}

};

#define nin(x) ((x)<<1)

#define nou(x) (((x)<<1)|1)

matrix a, s;

int n, m, t, x, y;

edge e[maxn];

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d%d%d%d%d", &n, &m, &t, &x, &y);

n = 0;

for (int i = 0; i < m; ++ i) {

int u, v;

scanf("%d%d", &u, &v);

e[n ++] = edge(u, v);

e[n ++] = edge(v, u);

}

e[n ++] = edge(-1, x);

e[n ++] = edge(y, -2);

a = matrix(n);

for (int i = 0; i < n; ++ i)

for (int j = 0; j < n; ++ j)

if (i != j && (i ^ j ^ 1) && e[i]. b == e[j]. a)

a. a[i][j] = 1;

s = matrix(n, 1);

for (++ t; t; t >>= 1, a = a * a)

if (t & 1)

s = s * a;

printf("%d\n", s. a[n - 2][n - 1]);

}