[SCOI2009] 迷路

题目类型：拆点， 矩阵快速幂

转化为矩阵快速幂，好题！

传送门：>Here<

解题思路

如果题目给出的是一个\(01\)矩阵，那么直接矩阵快速幂解决。详见How many ways??

然而带权了怎么办？

转化为01矩阵！容易发现题目给出的矩阵权值小于10，因此每个点拆成10个点，顺次连接权值为1的边。然后若\((u,v)\)之间距离为\(d\)，那么将\(u\)的第\(d-1\)个点连一条1的边到\(v\)的第一个点。

然后矩阵快速幂解决！

反思

看到这种相似的问题，很有可能用一种巧妙的方法将其转化为已知的经典问题。用矩阵快速幂求解路径方案数实在是经典到不能再经典了，再加上题目输入矩阵的特殊性，拆点就非常自然了。

Code

新的一种矩阵快速幂的写法，用的是一个结构体，让矩阵乘法变为一个函数。这样貌似在做快速幂的时候思路更清晰一些。然而码量增多了……

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 10010;

const int MAXM = 20010;

const int MOD = 2009;

const int INF = 1061109567;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = 0; int w = 1; register char c = getchar();

    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());

    if(c == '-') w = -1, c = getchar();

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;

}

struct Matrix{

	int a[110][110];

	inline void clear(){

		memset(a, 0, sizeof a);

	}

};

int N,T,dis;

Matrix g,ans;

char s[20];

inline Matrix mul(Matrix a, Matrix b){

	Matrix res,tmp;

	res.clear();

	tmp.clear();

	for(int i = 1; i <= N*10; ++i){

		for(int j = 1; j <= N*10; ++j){

			tmp.a[i][j] = 0;

			for(int k = 1; k <= N*10; ++k){

				tmp.a[i][j] = (tmp.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;

			}

		}

	}

	for(int i = 1; i <= N*10; ++i){

		for(int j = 1; j <= N*10; ++j){

			res.a[i][j] = tmp.a[i][j];

		}

	}

	return res;

}

inline void quick_power(int y){

	while(y > 0){

		if(y & 1){

			ans = mul(ans, g);

		}

		y /= 2;

		g = mul(g, g);

	}

}

int main(){

	scanf("%d%d", &N, &T);

	for(int i = 1; i <= N; ++i){

		for(int j = 1; j < 10; ++j){

			g.a[(i-1)*10+j][(i-1)*10+j+1] = 1;

		}

	}

	for(int i = 1; i <= N; ++i){

		scanf("%s", s);

		for(int j = 0; j < N; ++j){

			dis = s[j]-'0';

			if(dis > 0){

				g.a[(i-1)*10+dis][(j)*10+1] = 1;

			}

		}

	}

	for(int i = 1; i <= N*10; ++i) ans.a[i][i] = 1;

	quick_power(T);

	printf("%d", ans.a[1][(N-1)*10+1] % MOD);

	return 0;

}