Codevs 1482 路线统计(矩阵乘法)

本文主要是介绍Codevs 1482 路线统计(矩阵乘法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}