「矩阵乘法」迷路

传送门

一直不是很会做矩阵类的题(其实是什么题都不会做)。

积累了新思路（脑洞）：

发现如果边权只有0跟1,那么就是最简单的快速幂问题。但边权并不是，不过边权很小，只有1 ～ 9，所以我们可以在原有的矩阵上扩展一些虚点，将大于1的边权用1来表示出来。

其实这样用简单的问题来组合出复杂问题的思路还是挺常见的。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100;
int n, m;
int base[maxn][maxn], tmp[maxn][maxn], c[maxn][maxn];
void Matpow(int t) {
    for (int i = 1; i <= n * 9; i++)
	for (int j = 1; j <= n * 9; j++)
	    tmp[i][j] = (i == j ? 1 : 0);
    while (t) {
	if (t & 1) {
	    memset(c, 0, sizeof c);
	    for (int i = 1; i <= n * 9; i++) {
		for (int j = 1; j <= n * 9; j++) {
		    for (int k = 1; k <= n * 9; k++) {
			c[i][j] += tmp[i][k] * base[k][j];
		    }
		    if (c[i][j] >= 2009) c[i][j] %= 2009;
		}
	    }
	    for (int i = 1; i <= n * 9; i++)
		for (int j = 1; j <= n * 9; j++)
		    tmp[i][j] = c[i][j];
	}
	memset(c, 0, sizeof c);
	for (int i = 1; i <= n * 9; i++) {
	    for (int j = 1; j <= n * 9; j++) {
		for (int k = 1; k <= n * 9; k++) {
		    c[i][j] += base[i][k] * base[k][j];
		}
		if (c[i][j] >= 2009) c[i][j] %= 2009;
	    }
	}
	for (int i = 1; i <= n * 9; i++)
	    for (int j = 1; j <= n * 9; j++)
		base[i][j] = c[i][j];
	t >>= 1;
    }
}
int main() {
    scanf("%d %d", &n, &m);
    int x;
    for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= 8; j++)
	    base[i + j * n][i + (j - 1) * n] = 1;
	for (int j = 1; j <= n; j++) {
	    scanf("%1d", &x);
	    if (x) base[i][j + n * (x - 1)] = 1;
	}
    }
    Matpow(m);
    printf("%d
", tmp[1][n]);
    return 0;
}