题目传送门(BZOJ)
>原文链接<

题解 :

有向图,边权很小,拆点矩乘

因为边权不大于9,故把每个点拆成十份,$P(i, j)$ 代表距离到点$i$还有$j$个单位长度。

直接建立邻接矩阵,$P(i,j)$向$P(i, j-1)$连边。

由于矩阵乘法的性质,我们乘一次边表矩阵,相当于走了一步,直接考虑矩阵中点$i, j$ 是怎么乘来的。

维护方案数,正好利用乘法原理,求边表矩阵的T次方即可。T很大,矩阵快速幂优化。

请注意,边表矩阵转移只能转移边权全为1的图。

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define P(i, j) ((j-1)*n+i)using namespace std;const int N = 100;const int p = 2009;int n, m, T;struct Mat { int a[N][N]; Mat(){memset(a, 0, sizeof a);} int* operator [] (int cur) { return a[cur]; } void operator *= (Mat &b) { Mat c; for(int i = 1; i <= m; i ++ ) for(int j = 1; j <= m; j ++ ) for(int k = 1; k <= m; k ++ ) c[i][j] = (c[i][j]+a[i][k]*b[k][j])%p; *this = c; // 调用该运算符的结构体变量 } Mat operator ^ (int y) { Mat ret; for(int i = 1; i <= n; i ++ ) ret[i][i] = 1; while(y) { if(y&1) ret *= *this; *this *= *this; y >>= 1; } return ret; }}x;int main() { scanf("%d%d", &n, &T); m = n*9; for(int i = 1; i <= n; i ++ ) for(int j = 2; j <= 9; j ++ ) { x[P(i, j)][P(i, j-1)] = 1; } for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) { int u; scanf("%1d", &u); if(!u) continue; x[i][P(j, u)] = 1; } printf("%d\n", (x^T).a[1][n]);}