LOJ 10225 迷路

题目链接

如果边权都是\(1\)，那么矩阵\(i,j\)表示的就是单位时间\(i\)到\(j\)的方案数。
假设\(f-t\)表示在\(t\)时刻的方案数矩阵，\(f-t[i][j]=\sum\limits_{k=1}^{n}=f_{t-1}[i][k]*f_{1}[k][j]\)
显然是可以用矩阵乘法直接算的。
即\(f-t=f_{t-1}*f-1\)

那么现在边权不为\(1\)了，拆点，把每个点拆成\(w\)个，每个假点向上一个点连一条边。
\(u\)，\(v\)直接有\(w\)的边，就\(f[u][w-1]\)向\(f[v][1]\)连边。
一样的矩阵乘法就可以了。

#include <bits/stdc++.h>
using namespace std;

const int N = 100, MOD = 2009;
int n, m, T;

int pos(int i, int j) {return (i - 1) * 9 + j;}

struct Martix {
	int x, y, f[N][N];
	Martix (int X, int Y) {
        x = X, y = Y;
		memset(f, 0, sizeof f);
	}
	Martix operator * (const Martix& q) const {
		Martix t(x, q.y);
		for (int i = 1; i <= t.x; i++)
			for (int j = 1; j <= t.y; j++)
				for (int k = 1; k <= y; k++) t.f[i][j] = (1ll * t.f[i][j] + f[i][k] * 1ll * q.f[k][j]) % MOD;
		return t;
	}
};
char s[N];

int main() {
    scanf("%d %d", &n, &T);
    Martix a(n * 9, n * 9);
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j < 9; j++) a.f[pos(i, j)][pos(i, j + 1)] = 1;
    	scanf("%s", s + 1);
    	for (int j = 1; j <= n; j++) {
            int x = s[j] - '0';
            if (x >= 1) a.f[pos(i, x)][pos(j, 1)] = 1;
    	}
    }
    Martix ans(9 * n, 9 * n);
    for (int i = 1; i <= 9 * n; i++) ans.f[i][i] = 1;
    for (; T; T >>= 1, a = a * a) if (T & 1) ans = ans * a;
    printf("%d\n", ans.f[pos(1, 1)][pos(n, 1)]);
    return 0;
}