题意描述

给出一个有 $n$ 个节点的带权有向图,节点从 $1$ 至 $n$ 编号。

$\text{windy}$ 从节点 $1$ 出发,他必须恰好在 $t$ 时刻到达节点 $n$。

请告诉 $\text{windy}$ 总共有多少种不同的路径。

答案对 $2009$ 取模。

注意:$\text{windy}$ 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。


输入格式

第一行包含两个整数,分别代表 $n$ 和 $t$。

第 $2$ 到第 $(n + 1)$ 行,每行一个长度为 $n$ 的字符串。

其中,第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符,若为 $0$,则代表节点 $i$ 到节点 $j$ 无边。

否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$。


输出格式

输出一行一个整数代表答案对 $2009$ 取模的结果。


Input & Output ‘s examples

Input ‘s eg 1

2 2
11
00

Output ‘s eg 1

1

Input ‘s eg 2

5 30
12045
07105
47805
12024
12345

Output ‘s eg 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$。

保证边权$∈ \lbrack 0,9 \rbrack$


分析

这题 + 【NOI Online3】魔法值 = 【NOI2020】美食家

拆点的套路题。

题目数据里的 $n$ 很小强烈暗示邻接矩阵

考虑边权全部为 $1$ 时怎么做。若边权全部为 $1$ 则直接求出邻接矩阵的$k$ 次方即可。

之后考虑如何拓展到本题上。

仔细读一下题,可以发现本题的边权范围均在 $\lbrack 0 , 9 \rbrack$ 之内。则我们考虑将一个点拆为 $9$ 个点。对于点 $i$,我们将其拆为

其中点 $(i - 1) \times 9 + 1$ 为点 $i$ 的主点,然后对 $(i - 1) \times 9 + x$ 与 $(i - 1)\times 9 + x + 1$ 之间连接一条边长为 $1$ 的边。

这样连边权不为 $1$ 的边就很简单了。对于一条从 $u$ 到 $v$,边权为 $d$ 的边,我们只需要连接 $(u - 1) \times 9 + d$ 与 $(v - 1) \times 9 + 1$ 即可。

最后的答案就是 $1$ 的主点与 $n$ 的主点间的距离,即 $1$ 与 $(n - 1) \times 9 + 1$ 之间的距离。矩阵快速幂即可求解。

时间复杂度 $O(l^3 \log t)$,其中 $l = 9 \times n$,足以通过本题。

剩下的细节见代码即可。


Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 2009;

struct Matrix{
ll data[105][105];
};

Matrix operator * (const Matrix &A , const Matrix &B){
Matrix C; clean(C.data , 0);
rep(i , 0 , 100){
rep(j , 0 , 100){
rep(k , 0 , 100){
C.data[i][j] += A.data[i][k] * B.data[k][j];
C.data[i][j] %= HA;
}
}
}
return C;
}

Matrix Pow(Matrix A , ll k){
Matrix B; clean(B.data , 0);
rep(i , 1 , 100) B.data[i][i] = 1;

while(k){
if(k & 1) {
B = B * A;
}
A = A * A;
k >>= 1;
}
return B;
}

char s[M];

Matrix A , ans;

int main() {
#ifdef LOCAL
freopen("try.in" , "r" , stdin);
freopen("try1.out" , "w" , stdout);
#endif
ll n , t;
read(n) , read(t);
rep(i , 1 , n){
int now = (i - 1) * 9;
rep(j , 1 , 8){
A.data[now + j][now + j + 1] = 1;
}
}
rep(i , 1 , n){
scanf("%s" , s + 1);
int now = (i - 1) * 9;
rep(j , 1 , n){
if(s[j] == '0') continue;
else{
int dis = (int)(s[j] - '0');
A.data[now + dis][(j - 1) * 9 + 1] = 1;
}
}
}
clean(ans.data , 0);
rep(i , 1 , 10 * n) ans.data[i][i] = 1;
ans = Pow(A , t);
printf("%lld\n" , ans.data[1][(n - 1) * 9 + 1]);

return 0;
}

THE END