【BZOJ 1875】【SDOI 2009】HH去散步

水啊水，最后ans别忘了%哦！

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int mo = 45989;

int cnt = 1, point[23], n, m, t, S, T;

struct node {

	int u, v, nxt;

} E[1003];

struct Mt {

	int v[123][123];

	Mt() {memset(v, 0, sizeof(v));}

	friend Mt operator * (Mt a, Mt b) {

		Mt ans;

		for(int i = 1; i <= cnt; ++i)

			for(int j = 1; j <= cnt; ++j)

				for(int k = 1; k <= cnt; ++k)

					ans.v[i][j]=(ans.v[i][j] + a.v[i][k] * b.v[k][j]) % mo;

		return ans;

	}

	friend Mt operator ^ (Mt a, int b) {

		Mt ans;

		for(int i = 1; i <= cnt; ++i)

			ans.v[i][i] = 1;

		for(int i = b; i; i >>= 1, a = a * a)

			if (i & 1) ans = ans * a;

		return ans;

	}

}A, B;

inline void ins(int x, int y) {E[++cnt].u = x; E[cnt].v = y; E[cnt].nxt = point[x]; point[x] = cnt;}

int main() {

	scanf("%d%d%d%d%d", &n, &m, &t, &S, &T);

	int u, v;

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

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

		ins(u, v);

		ins(v, u);

	}

	for(int tmp = point[S]; tmp; tmp = E[tmp].nxt)

		++A.v[1][tmp];

	for(int i = 2; i <= cnt; ++i)

		for(int j = 2; j <= cnt; ++j)

			if (E[i].v == E[j].u && i != (j ^ 1))

				++B.v[i][j];

	A = A * (B ^ (t - 1));

	int ans = 0;

	for(int tmp = point[T]; tmp; tmp = E[tmp].nxt)

		ans += A.v[1][tmp ^ 1];

	printf("%d\n", ans % mo);

	return 0;

}

hhh