隐藏
「bsoj5146」都市环游 - 动态规划+矩阵快速幂 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「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即可。


代码

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
#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;
}
姥爷们赏瓶冰阔落吧~