【NOIP2014八校聯考第1場第2試9.21】都市環遊

NO IMAGE

Description

因為SJY乾的奇怪事情過多,SJY收到了休假的通知,於是他準備在都市間來回旅遊。SJY有一輛車子,一開始行駛效能為0,每過1時間行駛效能就會提升1點。每個城市的道路都有效能要求。SJY一共有t時間休息,一開始他位於1號城市(保證1號城市道路要求為0),他希望在n號城市結束旅程。每次穿過一條城市間的路會花費1時間,當然他也可以停留在一個城市不動而花費1時間。當且僅當車子的行駛效能大於等於一個城市,我們才能到達那裡。SJY希望知道,旅遊的方案模10086後的答案。(只要在某一時刻通過的道路存在一條不相同,就算不同的方案)

Input

第一行三個數n,m,t,表示有n個城市m條道路t時間。
第二行n個數,hi表示第i個城市的道路效能要求。
第三到m 2行,每行兩個數u,v,表示城市u與城市v之間有一條單向道路連線(可能有重邊)。

Output

包括一個數字,表示旅遊的方案模10086。

Sample Input

5 17 7
0 2 4 5 3
1 2
2 1
1 3
3 1
1 4
4 1
4 5
5 4
5 3
4 1
2 1
5 3
2 1
2 1
1 2
2 1
1 3

Sample Output

245

Data Constraint

對於20%的資料,n<=10,t<=80;
對於50%的資料,n<=30,t<=80;
對於100%的資料,n<=70,m<=1000,t<=100000000,hi<=70。

The Solution

很容易想到這是個Dp
我們設f[i][j]表示第i時刻,到達第j點的方案總數。
那麼隨手推一推我們可以得到
f[i][j]=f[i−1][k]∗a[k][j]f[i][j] = f[i-1][k]*a[k][j]
其中a[k][j]表示k到j的路徑數。
但是這樣做顯然不能拿到滿分
滿分做法的話也很簡單,做一下矩陣乘法就好了
考慮到h<=70,那麼我們可以分段打程式
當t<=70時,暴力dp即可
否則則做矩乘。

CODE

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for (int i=a;i<=b;i  )
#define fd(i,a,b) for (int i=a;i>=b;i--)
#define N 75
#define INF 1 << 30
#define mo 10086
using namespace std;
typedef int arr[N][N];
arr f,a,g;
int h[1005];
int n,m,t;
int read(int &n)
{
char ch = ' ';
int q = 0, w = 1;
for (;(ch != '-') && ((ch < '0') || (ch> '9'));ch = getchar());
if (ch == '-') w = -1,ch = getchar();
for (; ch >= '0' && ch <= '9';ch = getchar()) q = q * 10   ch - 48;
n = q * w;
return n;
}
namespace ib {char b[100];}
inline void pint(int x)
{
if (x == 0)
{
putchar(48);
return;
}
if (x < 0) 
{
putchar('-');
x = -x;
}
char *s = ib :: b;
while (x) *(   s) = x % 10,x /= 10;
while (s != ib :: b) putchar((* (s --))   48);
}
void Mult(arr &x,arr &y,arr &ans)
{
arr t;
memset(t,0,sizeof(t));
fo(k,1,n)
fo(i,1,n)
if (x[i][k])
fo(j,1,n)
t[i][j] = (t[i][j]   x[i][k] * y[k][j]) % mo;
memcpy(ans,t,sizeof(ans));
}
void Pow(int n,arr &ans)
{
for (;n;n >>= 1,Mult(a,a,a))
if (n & 1) Mult(ans,a,ans);
}
int main()
{
freopen("xor4.in","r",stdin);
read(n),read(m),read(t);
fo(i,1,n) read(h[i]);
fo(i,1,m)
{
int x,y;
read(x),read(y);
a[x][y]   ;
}
fo(i,1,n) a[i][i]   ;
f[0][1] = 1;
fo(i,1,70)
fo(j,1,n)
fo(k,1,n)
if (i >= h[k] && a[j][k]) f[i][k] = (f[i][k]   f[i - 1][j] * a[j][k]) % mo;
if (t <= 70) pint(f[t][n]);
else
{
fo(i,1,n) g[i][i] = 1;
t -= 70;
Pow(t,g);
fo(i,1,n)
fo(k,1,n) f[71][k] = (f[71][k]   f[70][i] * g[i][k]   mo) % mo;
pint(f[71][n]);
}
return 0;   
}