首页 > 代码库 > [BZOJ 1875] [SDOI 2009] HH去散步【矩阵乘法】

[BZOJ 1875] [SDOI 2009] HH去散步【矩阵乘法】

2024-08-07 12:27:31   217人阅读

题目链接：BZOJ - 1875

 

题目分析：

　　这道题如果去掉“不会立刻沿着刚刚走来的路走回”的限制，直接用邻接矩阵跑矩阵乘法就可以了。然而现在加了这个限制，建图的方式就要做一些改变。如果我们把每一条边看做点建矩阵，那么每次从一条边出发都只会到其他的边，不能仍然在这条边上“停留”，所以这就可以满足题目的限制。将每条边拆成两条单向边，比如一条编号为 4，一条编号为 5。那么 4^1=5, 5^1=4。这样只要不从第 i 条边走到 i 或 i^1 就可以了。初始的矩阵中以 A 为起点的边到达的方案数为 1 ，其余为 0。最后将终点为 B 的边的方案数累加即为答案。、

　　这种将边与点灵活转化的思想十分巧妙，应注意。 

代码如下：

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 20 + 5, MaxM = 120 + 5, Mod = 45989;int n, m, t, A, B, TopA, TopB, Index, RT, Ans, a, b;int EA[MaxM], EB[MaxM];struct Edge{	int u, v;	Edge() {}	Edge(int a, int b) {		u = a; v = b;	}	} E[MaxM];struct Matrix {	int x, y, Num[MaxM][MaxM];	void SetXY(int xx, int yy) {		x = xx; y = yy;	}	void Clear(int nn) {		for (int i = 0; i < x; ++i) {			for (int j = 0; j < y; ++j) {				Num[i][j] = nn;			}		}	}} M0, MZ;Matrix Mul(Matrix A, Matrix B) {	Matrix ret;	ret.SetXY(A.x, B.y);	ret.Clear(0);	for (int i = 0; i < ret.x; ++i) {		for (int j = 0; j < ret.y; ++j) {			for (int k = 0; k < A.y; ++k) {				ret.Num[i][j] += A.Num[i][k] * B.Num[k][j];				ret.Num[i][j] %= Mod;			}		}	}	return ret;}Matrix Pow(Matrix A, int b) {	Matrix ret, f;	f = A;	ret.SetXY(f.x, f.y);	for (int i = 0; i <= ret.x; ++i) ret.Num[i][i] = 1;	while (b) {		if (b & 1) ret = Mul(ret, f);		b >>= 1;		f = Mul(f, f);	}	return ret;}int main() {	scanf("%d%d%d%d%d", &n, &m, &t, &A, &B);	Index = -1;	for (int i = 1; i <= m; ++i) {		scanf("%d%d", &a, &b);		E[++Index] = Edge(a, b);		E[++Index] = Edge(b, a);	}	MZ.SetXY(m * 2, m * 2);	MZ.Clear(0);	TopA = TopB = 0;	for (int i = 0; i <= Index; ++i) {		if (E[i].u == A) EA[++TopA] = i;		if (E[i].v == B) EB[++TopB] = i;		for (int j = 0; j <= Index; ++j) {			if (i != j && i != (j ^ 1) && E[i].v == E[j].u) 				MZ.Num[i][j] = 1;		}	}	M0.SetXY(1, m * 2); 	M0.Clear(0);	for (int i = 1; i <= TopA; ++i) M0.Num[0][EA[i]] = 1;	MZ = Pow(MZ, t - 1);	M0 = Mul(M0, MZ);	Ans = 0;		for (int i = 1; i <= TopB; ++i) {		Ans += M0.Num[0][EB[i]];		Ans %= Mod;	}	printf("%d\n", Ans);	return 0;}

　　

[BZOJ 1875] [SDOI 2009] HH去散步【矩阵乘法】


联系
我们