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

Description

Input

Output

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

## The Solution

f[i][j]=f[i−1][k]∗a[k][j]f[i][j] = f[i-1][k]*a[k][j]

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;
{
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);
fo(i,1,m)
{
int x,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;
}``````