Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1769 Solved: 1287
Description
windy在有向图中迷路了。 该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。
Input第一行包含两个整数,N T。 接下来有 N 行,每行一个长度为 N 的字符串。 第i行第j列为'0'表示从节点i到节点j没有边。 为'1'到'9'表示从节点i到节点j需要耗费的时间。
Output包含一个整数,可能的路径数,这个数可能很大,只需输出这个数除以2009的余数。
Sample Input【输入样例一】
2 2
11
00
【输入样例二】
5 30
12045
07105
47805
12024
12345
【输出样例一】
1
【样例解释一】
0->0->1
【输出样例二】
852
30%的数据,满足 2 <= N <= 5 ; 1 <= T <= 30 。 100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。
/**************************************************************
Problem: 1297
User: ictsing
Language: C++
Result: Accepted
Time:1800 ms
Memory:1476 kb
****************************************************************/
//BZOJ1297 [SCOI2009]迷路
/*
首先有一个常识:如果没有路径长度的要求,且给定的邻接矩阵只有0和1表示通与不通的话,从S->E走N次的方案数就是这个矩阵自乘N次后的(S,E)的数值。
我们观察到了一个细节:路径长度范围很小,只有0~9,而且N的范围也很小,只有10。
那么我们可以来拆点。什么意思呢?就是把一个点拆成9个,根据路径的长度来连边。比如路径长度为5,我们就用5条边来连接。构图够好后就是裸的矩阵乘法了。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,t;
const int mod = 2009;
char s[10+5];
struct matrix
{
int p[100+5][100+5];
int n;
}ans,a;
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
matrix operator * (matrix a,matrix b)
{
matrix c;c.n=a.n;
memset(c.p,0,sizeof(c.p));
for(int i=1;i<=a.n;i++)
for(int j=1;j<=b.n;j++)
for(int k=1;k<=a.n;k++)
c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%mod)%mod;
return c;
}
matrix quickpow(int b)
{
matrix res;res.n=a.n;
for(int i=1;i<=res.n;i++)
res.p[i][i]=1;
while(b)
{
if(b&1) res=res*a;
b>>=1;a=a*a;
}
return res;
}
int main()
{
n=read(),t=read();
a.n=n*9;
for(int i=1;i<=n;i++)
for(int j=1;j<=8;j++)
a.p[9*(i-1)+j][9*(i-1)+j+1]=1;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
for(int j=1;j<=n;j++)
if(s[j-1]>'0')
a.p[9*(i-1)+s[j-1]-'0'][9*(j-1)+1]=1;
}
ans=quickpow(t);
printf("%d\n",ans.p[1][n*9-8]);
return 0;
}
评论