目录
题目链接
题目内容
[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\)。
前置知识：矩阵快速幂
一个幂数k=\(\sum2^i\) \(i\) \(\in\) \(Z\)
所以快速幂板子就出来啦（）
#include<bits/stdc++.h>
using namespace std;
const int maxn=150;
const int m=1e9+7;
typedef long long intx;
int n;
intx k;
struct matrix{
intx num[maxn][maxn];
matrix(){memset(num,0,sizeof(num));}
void build(){for(int i=1;i<=n;++i) num[i][i]=1;} //单位矩阵
};matrix a,ans;
matrix operator*(const matrix &x,const matrix &y){
matrix z;
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
z.num[i][j]=(z.num[i][j]+x.num[i][k]*y.num[k][j]%m)%m;
}
}
}
return z;
}
void input(){
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&a.num[i][j]);
}
}
}
int main(){
input();
ans.build();
while(k){
if(k&1) ans=ans*a;
a=a*a;
k=k>>1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
printf("%d ",ans.num[i][j]);
}
printf("\n");
}
return 0;
}
私货：话题#虚拟歌姬也会迷路吗#
思路历程
1.我寻思这图里咋还有自环呢
对角线还有值这自己和自己连边啊。
干不会了。
然后就看这个专题名字叫“矩阵快速幂”
但是我还没有打过板子所以速速去打了一下（）
2.ok快乐的板子时光总是短暂的（）
我想了想觉得边权肯定是附加的属性，于是我先不管边权只建边或许可以的得到一些启发：
好丑的图（）
嗯所以和矩阵有什么关系呢（其实当我画出这么多边的时候我就知道没什么用了）
怎么还越扯越远了（）
3.额我们还是不看边权，但是不扯到图上去了。
如果，我是说如果，这是个邻接矩阵：
样例1：
1 1
0 0
问有几种到达方法。
那么就是说1要一个一个点到达2，第一行都要有数。
也就是说啊，i可以一个一个点的到达j，意味着\(a_i,_2\) ———— \(a_i,_j\)要有数
那经过的每一个点又都有一个出度，出度就是第i行1的个数
是不是说从1起点能到达的点的出度相乘再除以2就是方案数呢？
那么样例2呢：
1 1 0 1 1
0 1 1 0 1
1 1 1 0 1
1 1 0 1 1
1 1 1 1 1
怎么感觉不太对啊……
话说我要是从点1到点5再回点1再到点5这算不算一种方案啊……
4.那我们现在加上边权吧
那该怎么算边权呢？
我们假设边权只有1
\(f_t[i,j]\)表示从i点到j点花费时间为t的方案数
就有了方程：
\(f_t=\sum\limits_{k=1}^{n}f_{t-1}[i,k]+f_1[k,j]\)
那\(f_t\)也就是\(f_1^t\)。
那就出来了a。
\(f_1\)就是最初的矩阵啊。
5.回归本题
本题的区别在于权值是1-9啊
1-9，1-9……
我想了想，我他喵的\(f_t\)是\(f_1^t\)
那\(f_9\)不就是\(f_1^9\)吗！！！
那我把这个边多拆成几条边。
反正是求不小于t的方案数。
但是我如何建边才能保证没有多得方案数啊。
总不能搁节点1和节点2之间塞点吧
……
去看看题解（）
……
我们1个点建9个小点，只有第0小点可以跨越小点的集合。
那么我们建立第i小点到第i-1小点的w=1的单向边
而要连的两个点1到点2则将小点集合1中的小点0和集合2中的小点w-1相连。
如下图（只画出了点1到点2经过的路径）
那么我们就转换成了边权都为1的9n*9n大小的矩阵。
代码实现：
注：与以上解释不同，代码中a[i][j]表示j指向i的边，并且不再设置第0小点改为设置第1小点为唯一可以外接点。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=12;
const int mod=2009;
char s[maxn];
int n,sn,t;
struct matrix{
int num[maxn*9][maxn*9];
void clear(){
memset(num,0,sizeof(num));
}
};matrix a;
matrix operator *(matrix x,matrix y){
matrix res;
res.clear();
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
res.num[i][j]=(res.num[i][j]+x.num[i][k]*y.num[k][j]%mod)%mod;
}
}
}
return res;
}
matrix operator ^(matrix x,int y){
matrix res;
res.clear();
for(int i=1;i<=n;++i){
res.num[i][i]=1; //单位矩阵
}
while(y){
if(y&1) res=res*x;
x=x*x;
y=y>>1;
}
return res;
}
void inner_link(){ //小点间建边
for(int i=1;i<=sn;++i){
for(int j=1;j<=8;++j){
a.num[9*(i-1)+j][9*(i-1)+j+1]=1;
}
}
}
void outer_link(){ //集合间建边
for(int i=1;i<=sn;++i){
scanf("%s",s+1);
for(int j=1;j<=sn;++j){
if(s[j]>'0'){
a.num[9*(i-1)+s[j]-'0'][9*(j-1)+1]=1;
}
}
}
}
int main(){
scanf("%d%d",&n,&t);
sn=n;
n*=9;
inner_link();
outer_link();
a=a^t;
printf("%d",a.num[1][sn*9-8]);
return 0;
}