首页 > 代码库 > BZOJ1297 [SCOI2009]迷路
BZOJ1297 [SCOI2009]迷路
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
2 2
11
00
【输入样例二】
5 30
12045
07105
47805
12024
12345
Sample Output
【输出样例一】
1
【样例解释一】
0->0->1
【输出样例二】
852
1
【样例解释一】
0->0->1
【输出样例二】
852
HINT
30%的数据,满足 2 <= N <= 5 ; 1 <= T <= 30 。 100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。
题解
令邻接矩阵中所有k组成的矩阵为$A_k$,$i$阶邻接矩阵为$T_i$,即$T_{i,a,b}$表示从$a$到$b$恰好走$i$的时间的方案数。
那么有
$$T_i = \sum_{j=1}^9 A_j * T_{i-j}$$
我们发现,如果我们把$A_j$和$T_i$都看做单个数,那么这就是经典的线性常系数递推方程,可以用矩阵快速幂解决。
$A_j,T_i$是矩阵也可以这么做,只是1变成了单位矩阵,0变成了零矩阵,递推矩阵变成了“矩阵的矩阵”(当然,在实现上,我们可以把它“拍扁”)。
那么直接强上矩阵快速幂就行了。
附代码:
#include <cstdio> #include <cstring> const int N = 15; const int mod = 2009; int nn; struct Matrix{ int v[N * 9][N * 9]; Matrix() { memset(v, 0, sizeof v); } friend Matrix operator*(const Matrix &a, const Matrix &b) { Matrix ans; for (int i = 0; i < nn; ++i) for (int j = 0; j < nn; ++j) if (a.v[i][j]) for (int k = 0; k < nn; ++k) ans.v[i][k] = (ans.v[i][k] + a.v[i][j] * b.v[j][k]) % mod; return ans; } }; Matrix D; Matrix ans; int main() { int n, t; scanf("%d%d", &n, &t); nn = n * 9; int x; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { scanf("%1d", &x); if (x) D.v[i][(x - 1) * n + j] = 1; } for (int i = 0; i < 8 * n; ++i) D.v[i + n][i] = 1; for (int i = 0; i < n; ++i) ans.v[i][i] = 1; for (; t; D = D * D, t >>= 1) if (t & 1) ans = ans * D; printf("%d\n", ans.v[0][n - 1]); return 0; }
BZOJ1297 [SCOI2009]迷路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。