[SCOI2009] 迷路
题目背景
windy 在有向图中迷路了。
题目描述
该有向图有 \(n\) 个节点,节点从 \(1\) 至 \(n\) 编号,windy 从节点 \(1\) 出发,他必须恰好在 \(t\) 时刻到达节点 \(n\)。
现在给出该有向图,你能告诉 windy 总共有多少种不同的路径吗?
答案对 \(2009\) 取模。
注意:windy 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。
输入格式
第一行包含两个整数,分别代表 \(n\) 和 \(t\)。
第 \(2\) 到第 \((n + 1)\) 行,每行一个长度为 \(n\) 的字符串,第 \((i + 1)\) 行的第 \(j\) 个字符 \(c_{i, j}\) 是一个数字字符,若为 \(0\),则代表节点 \(i\) 到节点 \(j\) 无边,否则代表节点 \(i\) 到节点 \(j\) 的边的长度为 \(c_{i, j}\)。
输出格式
输出一行一个整数代表答案对 \(2009\) 取模的结果。
样例 #1
样例输入 #1
2 2
11
00
样例输出 #1
1
样例 #2
样例输入 #2
5 30
12045
07105
47805
12024
12345
样例输出 #2
852
提示
样例输入输出 1 解释
路径为 \(1 \to 1 \to 2\)。
数据规模与约定
- 对于 \(30\%\) 的数据,保证 \(n \leq 5\),\(t \leq 30\)。
- 对于 \(100\%\) 的数据,保证 \(2 \leq n \leq 10\),\(1 \leq t \leq 10^9\)。
//思路来自https://www.luogu.com.cn/blog/user38725/solution-p4159
//发现边权只有1~9,所以我们可以暴力把一个点拆成9个点并按顺序连上
//然后一条边权为k的边就是从起点拆出的第k个点到终点拆出的第一个点连边
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod = 2009;
int n, t, num[521][13];
char ch[521];
struct Matrix {
int matrix[114][514];
}ask;
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
for (int i = 1; i <= n * 9; ++ i) {
for (int j = 1; j <= n * 9; ++ j) {
c.matrix[i][j] = 0;
for (int q = 1; q <= n * 9; ++ q) {
c.matrix[i][j] += (a.matrix[i][q] * b.matrix[q][j]);
c.matrix[i][j] %= mod;
}
}
}
return c;//矩阵乘
}
Matrix MatrixQuickPower(Matrix a,int k) {
Matrix ans, base = a;
for (int i = 1; i <= n * 9; ++ i) {
for (int j = 1; j <= n * 9; ++ j) {
if (i == j) ans.matrix[i][j] = 1;
else ans.matrix[i][j] = 0;
}
}
while (k > 0) {
if (k & 1 == 1) {
ans = ans * base;
}
base = base * base;
k >>= 1;
}
return ans;
//矩阵快速幂
}
int main() {
cin >> n >> t;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= 8; ++ j) {
ask.matrix[9 * (i - 1) + j][9 * (i - 1) + j + 1] = 1;
//将一个点内的每个点顺序连上
}
}
for (int i = 1; i <= n; ++ i) {
scanf("%s", ch + 1);
for (int j = 1; j <= n; ++ j) {
if (ch[j] > '0') {
ask.matrix[9 * (i - 1) + ch[j] - '0'][9 * (j - 1) + 1] = 1;
//把第i个点内的第k个点与第j个点的起始点连上
}
}
}
Matrix ans = MatrixQuickPower(ask, t);
//题目问的是从点1到点n的路径数
cout << (ans.matrix[1][n * 9 - 8]) % mod << endl;
return 0;
}
标签:Matrix,int,Luogu,样例,leq,SCOI2009,P4159,include,节点
From: https://www.cnblogs.com/jueqingfeng/p/17471732.html