当前位置:网站首页>BZOJ1875 [SDOI2009]HH去散步 【dp + 矩阵优化】

BZOJ1875 [SDOI2009]HH去散步 【dp + 矩阵优化】

2021-07-23 13:05:04 mb60f648e7599c6

题目

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

输入格式

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

输出格式

一行,表示答案。

输入样例

4 5 3 0 0

0 1

0 2

0 3

2 1

3 2

输出样例

4

题解

如果没有不能走回头路的限制,这道题就可以用邻接矩阵直接快速幂水过
但是有了这样的限制,我们需要重新考虑

注意到限制是路径中相邻的两个边不能是同一条边,注意到路径中相邻的点本就不会是同一个点
这启发我们可以将边点互换
把每条无向边拆成两条有向边,每条边分别向其指向的点为起点的边连线
这样子求出的邻接矩阵\(G\)\(G^t[i][j]\)就表示从\(i\)开始选出t条连续的边以\(j\)结束的方案数
经过\(t\)个点的路径只有\(t-1\)条边,故只需求出\(G^(t-1)\),然后统计A为起点的边到达B为终点的边的方案数

#include<iostream>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 55,maxm = 125,INF = 1000000000,P = 45989;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
	return out * flag;
}
vector<int> ed[maxn];
int n,m,t,S,T,a[maxm],b[maxm];
struct Matrix{
	int s[maxm][maxm],n,m;
	Matrix(){memset(s,0,sizeof(s)); n = m = 0;}
}G;
Matrix operator *(const Matrix& a,const Matrix b){
	Matrix ans;
	if (a.m != b.n) return ans;
	ans.n = a.n; ans.m = b.m;
	for (int i = 0; i < ans.n; i++)
		for (int j = 0; j < ans.m; j++)
			for (int k = 0; k < a.m; k++)
				ans.s[i][j] = (ans.s[i][j] + a.s[i][k] * b.s[k][j] % P) % P;
	return ans;
}
Matrix qpow(Matrix a,int b){
	Matrix ans; ans.n = ans.m = a.n;
	for (int i = 0; i < ans.n; i++) ans.s[i][i] = 1;
	for (; b; b >>= 1,a = a * a)
		if (b & 1) ans = ans * a;
	return ans;
}
int main(){
	n = read(); m = read(); t = read(); S = read(); T = read();
	G.n = G.m = 2 * m;
	int u,v,ans = 0;
	for (int i = 0; i < m; i++){
		a[i] = u = read(); b[i] = v = read();
		ed[u].push_back(i);
		ed[v].push_back(i + m);
	}
	for (int i = 0; i < m; i++){
		for (int j = 0; j < ed[b[i]].size(); j++)
			if (ed[b[i]][j] != i + m)
				G.s[i][ed[b[i]][j]] = 1;
		for (int j = 0; j < ed[a[i]].size(); j++)
			if (ed[a[i]][j] != i) G.s[i + m][ed[a[i]][j]] = 1;
	}
	Matrix F = qpow(G,t - 1);
	for (int i = 0; i < m; i++){
		if (a[i] == S){
			for (int j = 0; j < m; j++){
				if (b[j] == T) ans = (ans + F.s[i][j]) % P;
				if (a[j] == T) ans = (ans + F.s[i][j + m]) % P;
			}
		}
		if (b[i] == S){
			for (int j = 0; j < m; j++){
				if (b[j] == T) ans = (ans + F.s[i + m][j]) % P;
				if (a[j] == T) ans = (ans + F.s[i + m][j + m]) % P;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}


      
  • 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.

版权声明
本文为[mb60f648e7599c6]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15308415/3141797