1482 路线统计
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
N个节点的有向图, 求从start到finish刚好经过时间time的总方案数 mod 502630.
输入描述 Input Description
第一行包含一个整数n, 所有点是从0到N-1编号.
接下来n行,每行包含n个字符. 第i行第j个字符表示i到j需要的时间. 字符只可能是’1’到’5’, 或者是’.’表示i不能到达j. 保证主对角线都是’.’.
接下来一行3个整数start, finish, time.
输出描述 Output Description
输出总方案数.
样例输入 Sample Input
3
.12
2.1
12.
0 2 5
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
对于20%的数据, 输入的字符不是’1’就是’.’;
对于100%的数据, 1 <= n <= 10; 1 <= start,finish <= n; 1 <= time <= 10^9.
分类标签 Tags
矩阵乘法 数论
/*
矩阵乘法.
没想出来 唉.
比较神奇.
t为1的话直接矩阵乘法.
but 这题1<=t<=5啊.
这样的话我们考虑拆点.
拆成这样i1->i2->i3->i4->i5.
然后对于it(第t个点)连一条边到j.
这样我们每条边的长度就都是1啦.
然后就可以转移啦.
*/
#include<iostream>
#include<cstdio>
#define MAXN 101
#define LL long long
#define mod 502630
using namespace std;
int n,m,s,t,k;
LL ans[MAXN][MAXN],b[MAXN][MAXN],c[MAXN][MAXN];
void mi()
{
while(k)
{
if(k&1)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]=(c[i][j]+ans[i][k]*b[k][j])%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans[i][j]=c[i][j],c[i][j]=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]=(c[i][j]+b[i][k]*b[k][j])%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=c[i][j],c[i][j]=0;
k>>=1;
}
}
int main()
{
char ch;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<5;j++)
ans[i+(j-1)*n][i+j*n]=b[i+(j-1)*n][i+j*n]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>ch;
int x=int(ch-48);
if(ch!='.') ans[i+(x-1)*n][j]=b[i+(x-1)*n][j]=1;
}
scanf("%d%d%d",&s,&t,&k);
s++,t++;k--;
n*=6;
mi();
cout<<ans[s][t];
return 0;
}