题意描述

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

windy 从节点 1 出发,他必须恰好在 t 时刻到达节点 n

请告诉 windy 总共有多少种不同的路径。

答案对 2009 取模。

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


输入格式

第一行包含两个整数,分别代表 nt

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

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

否则代表节点 i 到节点 j 的边的长度为 ci,j


输出格式

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


Input & Output ‘s examples

Input ‘s eg 1

markdown
2 2
11
00

Output ‘s eg 1

markdown
1

Input ‘s eg 2

markdown
5 30
12045
07105
47805
12024
12345

Output ‘s eg 2

markdown
852

数据范围和约定

对于 30% 的数据,保证 2n51t30

对于 100% 的数据,保证 2n101t109

保证边权[0,9]


分析

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

拆点的套路题。

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

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

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

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

{(i1)×9+x,x[1,9]}

其中点 (i1)×9+1 为点 i 的主点,然后对 (i1)×9+x(i1)×9+x+1 之间连接一条边长为 1 的边。

这样连边权不为 1 的边就很简单了。对于一条从 uv,边权为 d 的边,我们只需要连接 (u1)×9+d(v1)×9+1 即可。

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

时间复杂度 O(l3logt),其中 l=9×n,足以通过本题。

剩下的细节见代码即可。


Code[Accepted]

cpp
#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