【SCOI2009】迷路-题解

题意描述

给出一个有 $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\mathrm{\%}$ 的数据，保证 $2\le n\le 5$，$1\le t\le 30$。

对于 $100\mathrm{\%}$ 的数据，保证 $2\le n\le 10$，$1\le t\le {10}^9$。

保证边权$\in [0,9]$

---

分析

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

拆点的套路题。

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

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

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

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

$$\{(i-1)\times 9+x,x\in [1,9]\}$$

其中点 $(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