「bsoj5146」都市环游 - 动态规划+矩阵快速幂

题目大意

    因为SJY干的奇怪事情过多，SJY收到了休假的通知，于是他准备在都市间来回旅游。SJY有一辆车子，一开始行驶性能为$0$，每过$1$时间行驶性能就会提升$1$点。每个城市的道路都有性能要求。SJY一共有$t$时间休息，一开始他位于$1$号城市（保证$1$号城市道路要求为$0$），他希望在$n$号城市结束旅程。每次穿过一条城市间的路会花费$1$时间，当然他也可以停留在一个城市不动而花费$1$时间。当且仅当车子的行驶性能大于等于一个城市，我们才能到达那里。SJY希望知道，旅游的方案模$10086$后的答案。（只要在某一时刻通过的道路存在一条不相同，就算不同的方案）

---

题目分析

观察数据范围，发现$h_i$远小于$t$。
因此当$t\gt\max(h_i)$时，原图无限制，可以随意走动。问题转化为求原图移动$t-\max(h_i)$次后到达$n$的方案数，这部分可以使用邻接矩阵的快速幂实现。

那么当$t\le\max(h_i)$时呢？范围这么小，直接暴力Dp即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

typedef long long LL;
const int maxn=75,mod=10086;
struct Matrix {
	LL n,m,a[maxn][maxn];
	Matrix(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	Matrix(LL n,LL m,char E) { //单位矩阵
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
		for(int i=1; i<=n; i++)a[i][i]=1;
	}
	void init(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	LL* operator [] (const LL x) {
		return a[x];
	}
	Matrix operator * (Matrix& b) {
		Matrix c(n,b.m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=b.m; j++)
				for(int k=1; k<=m; k++)
					c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
		return c;
	}
	void operator *= (Matrix& b) {
		*this=*this*b;
	}
	Matrix operator ^ (LL b) {
		Matrix ans(n,m,'e'),a=*this;
		while(b>0) {
			if(b&1)ans=ans*a;
			a*=a;
			b>>=1;
		}
		return ans;
	}
};

int n,m,t,a[maxn],map[maxn][maxn],f[maxn][maxn],Max=0,ans=0;

int Dp(int Now,int Time) {
	if(!Time)return Now==1;
	if(Time<a[Now])return 0;
	if(~f[Now][Time])return f[Now][Time];
	f[Now][Time]=0;
	for(int i=1; i<=n; i++)
		if(map[i][Now])f[Now][Time]=(f[Now][Time]+map[i][Now]*Dp(i,Time-1))%mod;
	return f[Now][Time];
}

int main() {
	n=Get_Int();
	m=Get_Int();
	t=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Get_Int();
		Max=max(Max,a[i]);
		map[i][i]++;
	}
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		map[x][y]++;
	}
	memset(f,-1,sizeof(f));
	if(t<=Max) {
		printf("%d\n",Dp(n,t));
		return 0;
	}
	Matrix A(n,n);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			A[i][j]=map[i][j];
	A=A^(t-Max);
	for(int st=1; st<=n; st++)ans=(ans+A[st][n]*Dp(st,Max))%mod;
	printf("%d\n",ans);
	return 0;
}