[SCOI 2009]迷路

传送门

问题描述

Windy 在有向图中迷路了。 该有向图有 \({N}\) 个节点,Windy 从节点 \({1}\) 出发,他必须恰好在 \({T}\) 时刻到达节点 \({N}\)
现在给出该有向图,你能告诉 Windy 总共有多少种不同的路径吗?
注意:Windy 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。

输入格式:

第一行包含两个整数,\({N,T}\)
接下来有 \({N}\) 行,每行一个长度为 \({N}\) 的字符串。第 \({i}\) 行第 \({j}\) 列为 \({0}\) 表示从节点 \({i}\) 到节点 \({j}\) 没有边,为 \({1}\)\({9}\) 表示从节点 \({i}\) 到节点 \({j}\) 需要耗费的时间。

输出格式:

包含一个整数,可能的路径数,这个数可能很大,只需输出这个数除以 \({2009}\) 的余数。

样例输入1:

2 2
11
00

样例输出1:

1

样例说明1:

\({1→1→2}\)

样例输入2:

5 30
12045
07105
47805
12024
12345

样例输出2:

852

说明:

对于 \({ 30 \% }\) 的数据,满足 \({2 \leq N \leq 5,1 \leq T \leq 30}\)
对于 \({ 100 \% }\) 的数据,满足 \({2 \leq N \leq 10,1 \leq T \leq 10^9}\)

分析

1.这dio图里怎么还有自环呢?

哦 凑时间用的

2.既然是个图 那就画出来看看叭(过于抽象以至于未完成)


实在蚌埠住了

3.乂~它在矩阵快速幂专题里面诶,那就先打个板子叭

(打板子ing)
既然是矩阵快速幂,那肯定要推递推式啊

                          \({\large 试试就逝世}\)

假如输入是个邻接矩阵
我们先不看边权(假设边权都为1) 无权的都推不出来还推什么带权的

显而易得

这个邻接矩阵自乘\({T}\)次之后 \({a[1][n]}\) 就是答案

\({F[i,j]}\)表示\({i \sim j}\)
若有连边则说明\({i \sim j}\)有一种路径
那么\({a[i][k]*a[k][j]}\)就相当于从\({i}\)走到\({k}\)的方案数乘以从\({k}\)\({j}\)的方案数
将所有的\({a[i][k]*a[k][j]}\)加起来 就能得到多走\({1}\)的方案数
于是就有了方程:
                      \({\large F_t=\sum_{k=1}^n {F_{t-1}}[i,k] * F_1[k,j]}\)

所以\({F_1}\)就是最原始的矩阵aaaaaaaaa

但问题在于 这个矩阵的边权不为\({1}\)aaaaaaaaaaa

————————————————————
问佬佬()
。。。。。。。。。。。。。。。。。。。。。。
学成归来
————————————————————

于是我们知道了一个叫做拆点的东东

由于上限为9
我们将\({1}\)个点拆成\({9}\)个点,第\({i}\)个点拆成的第\({j-1}\)个点向第\({j}\)个点连一条边权为\({1}\)的边
那么\({i \sim j}\)有一条边权为\({k}\)的边等价于\({i}\)\({j}\)拆成的第\({k}\)个点连边

最后再跑一遍矩阵快速幂就好啦~~~

code

Elaina’s code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define INF 0x7fffffff
#define mst(a,b) memset(a,b,sizeof(a))
#define Elaina 0
const int N = 15;
const int mod = 2009;
int n,sn,t;

struct Mat{
	int n,m;
	int a[N*9][N*9];
	void clean(){
		mst(a,0);
	}
	void unit(){
		clean();
		for(int i=1;i<=n;i++){
			a[i][i]=1;
		}
	}
	void resize(int x,int y){ 
		n=x,m=y;
	}
	Mat operator * (const Mat &A) const {
		Mat res;
		res.resize(n,n);
		res.clean();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
					res.a[i][j]=(a[i][k]*A.a[k][j]+res.a[i][j])%mod;
				}
			}
		}
		return res;
	}
};

Mat qpow(Mat A,int b){
	Mat res;
	res.resize(n,n);
	res.unit();
	while(b){
		if(b&1){
			res=res*A;
		}
		A=A*A;
		b>>=1;
	}
	return res;
}
Mat mat;
signed main(){
	cin>>n>>t;
	sn=n;
	n*=9;
	char x[N];
	
	mat.resize(n,n);
    
    //拆分大点为小点
	for(int i=1;i<=sn;i++){
		for(int j=1;j<=8;j++){
			mat.a[(i-1)*9+j+1][(i-1)*9+j]=1;
		}
	}

    //大点这个集合建边
	for(int i=1;i<=sn;i++){
		scanf("%s",x+1);
		for(int j=1;j<=sn;j++){
			if(x[j]>'0'){
				mat.a[(j-1)*9+1][(i-1)*9+x[j]-'0']=1;
			}
		}
	}
	mat=qpow(mat,t);
	cout<<mat.a[sn*9-8][1]%mod;
	return Elaina;
}

都看到这了,真的不点个赞吗(>ω<*)