BZOJ 1875: [SDOI2009]HH去散步

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径

Input

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但不保证任意两个路口之间至多只有一条路相连接。路口编号从0到N − 1。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模45989。

Output

一行，表示答案。

Sample Input

4 5 3 0 0

0 1

0 2

0 3

2 1

3 2

Sample Output

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Solution

设dp[i][j][k]表示走了i步，最后一步是从j走到k的方案数。列出转移方程来，转移就行了。这题t比较大，因此我们用矩阵乘法+快速幂来搞。

注意开始节点和结束节点是给定的！可能有重边！蒟蒻因为这个调了一晚上QAQ

还有需要注意的是矩阵中每个位置的值的含义，不要搞混了。蒟蒻A数组初始值自带×1，因此要–t，其实也可以把初始值看成有状态[0][0][a]的dp，那样的话就不用–t，初始值dp[0][0][a]=1，直接上矩阵乘法+快速幂。

Code

  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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const unsigned mod = 45989;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int a, b, n, m, N;
struct Matrix_type {
	unsigned a[150][150];
	void init1() {
		for (int i = 0; i < N; ++i)
			a[i][i] = 1;
	}
};
Matrix_type temp;
int t;
void mul(Matrix_type &A, Matrix_type &B) {
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) {
			temp.a[i][j] = 0;
			for (int k = 0; k < N; ++k) {
				temp.a[i][j] = (temp.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
			}
		}
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			A.a[i][j] = temp.a[i][j];
}
unsigned C[150];
void mul(unsigned *A, Matrix_type &B) {
	for (int j = 0; j < N; ++j) {
		C[j] = 0;
		for (int k = 0; k < N; ++k) {
			C[j] = (C[j] + A[k] * B.a[k][j] % mod) % mod;
		}
	}
	for (int i = 0; i < N; ++i)
		A[i] = C[i];
}
Matrix_type tmp, mat;
void KSM() {
	while (t) {
		if (t & 1)
			mul(mat, tmp);
		mul(tmp, tmp);
		t >>= 1;
	}
}
int id[150][150], ex[150], ey[150], EX[150], EY[150], eid[150];
unsigned A[150], cnt[150];
bool cmp(int x, int y) {
	return ex[x] == ex[y] ? ey[x] < ey[y] : ex[x] < ex[y];
}
int main() {
	scanf("%d%d%d%d%d", &n, &m, &t, &a, &b);
	if (t == 0) {
		putchar('0');
	} else {
		++a; ++b; 
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j <= n; ++j)
				id[i][j] = -1;
		int x, y;
		N = m << 1;
		for (int i = 0; i < m; ++i) {
			scanf("%d%d", &x, &y);
			++x; ++y;
			ex[i<<1] = x; ey[i<<1] = y;
			eid[i<<1] = i<<1;
			ex[i<<1|1] = y; ey[i<<1|1] = x;
			eid[i<<1|1] = i<<1|1;
		}
		N = m << 1; ex[N] = ey[N] = -1;
		sort(eid, eid+N, cmp);
		int tot = 0, Cnt = 1;
		for (int i = 0; i < N; ++i) {
			int j = eid[i], k = eid[i+1];
			if (ex[j] == ex[k] && ey[j] == ey[k]) {
				++Cnt;
			} else {
				EX[tot] = ex[j]; EY[tot] = ey[j];
				id[ex[j]][ey[j]] = tot++;
				cnt[id[ex[j]][ey[j]]] = Cnt;
				Cnt = 1;
			}
		}
		N = tot;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (EY[i] != EX[j])
					tmp.a[i][j] = 0;
				else {
					tmp.a[i][j] = cnt[j];
					if (EX[i] == EY[j])
						--tmp.a[i][j];
				}
			}
		}
		for (int i = 1; i <= n; ++i)
			if (id[a][i] != -1)
				A[id[a][i]] = cnt[id[a][i]];
		--t;
		mat.init1();
		KSM();
		mul(A, mat);
		int ans = 0;
		for (int i = 1; i <= n; ++i)
			if (id[i][b] != -1)
				ans = (ans + A[id[i][b]]) % mod;
		printf("%d", ans);
	}
	return 0;
}