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

4

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

#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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据