题目描述
windy在有向图中迷路了。 该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。
输入格式
第一行包含两个整数,N T。 接下来有 N 行,每行一个长度为 N 的字符串。 第i行第j列为’0’表示从节点i到节点j没有边。 为’1’到’9’表示从节点i到节点j需要耗费的时间。
输出格式
包含一个整数,可能的路径数,这个数可能很大,只需输出这个数除以2009的余数。
输入输出样例
输入 #1
2 2
11
00
输出 #1
1
输入 #2
5 30
12045
07105
47805
12024
12345
输出 #2
852
说明/提示
【样例解释一】
0->0->1
【数据范围】
30%的数据,满足 2 <= N <= 5 ; 1 <= T <= 30 。
100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。
解释:如果边都是1的话,很简单,所以我们就想办法把它转行成边为1,我们对每个点进行扩充到9个,这样的话,每条边长为1,得到矩阵后直接矩阵快速幂即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 120
#define mod 2009
#define ll int
using namespace std;
int G[N][N]={0};
int n=0,T=0;
int m=0;
char str[123];
class Matrix{
public:
ll a[N][N],n;
Matrix(int _n){
n=_n;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) a[i][i]=1%mod;
}
int get(int x,int y){
return a[x][y];
}
void set(int x,int y,int val){
a[x][y]=val%mod;
}
void mul(Matrix &b){
int c[N][N]={0};
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c[i][j]+=a[i][k]*b.a[k][j]%mod;
c[i][j]%=mod;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) a[i][j]=c[i][j];
}
void pow(ll k){
Matrix ret(n);
while(k){
if(k&1){
ret.mul(*this);
}k>>=1;
this->mul(*this);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) a[i][j]=ret.a[i][j]%mod;
}
void display(){
for(int i=1;i<=n;i++){
printf("%d",a[i][1]);
for(int j=2;j<=n;j++){
printf(" %d",a[i][j]);
}
printf("\n");
}
}
};
int main(){
cin>>n>>T;
m=n*9;
Matrix mk(m);
for(int i=1;i<=n;i++){
cin>>(str+1);
for(int j=1;j<=n;j++){
int pos=(i-1)*9+1;
int y=str[j]-'0';
if(y<1) continue;
for(int k=2;k<=y;k++){
G[pos][pos+1]=1;
pos++;
}
G[pos][(j-1)*9+1]=1;
}
}
for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) mk.a[i][j]=G[i][j];
mk.pow(T);
cout<<mk.a[1][(n-1)*9+1]<<endl;
return 0;
}