题意

洛谷的翻译太直接的吧。

有一个 $n$ 个点 $m$ 条边的图，第 $i$ 条边有 $p_{i,j}$ 条长度为 $j$ 的路。现在从 $1$ 点出发，求走长度恰好为 $T$ 的路径后回到 $1$ 的方案数。

模 $998244353$。

$1 \le n,m \le 10,1 \le T \le 4 \times 10^4$。

分析

这题 $n,m$ 很小，我们考虑可以 dp。设 $f_{i,j}$ 表示走到点 $i$，走了 $j$ 的长度的方案数。初始状态 $f_{1,0} = 1$。

考虑转移。

$$f_{u,i} = \sum_{E_k = (u,v)} \sum_{j=0}^{i-1} f_{v,j}p_{k,i-j}$$

这个式子长得异常清秀，发现这个式子就是 分治 FFT 的式子。暴力做是 $O(mT^2)$ 的。考虑优化。

我们按照分治 FFT 的做法做，时间复杂度可以做到 $O(mT\log^2T)$，这个是容易的，按照板子做即可。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define poly vector <int>
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int N = (1 << 20) + 5;
namespace Poly{
    int rev[N];
    const int P = 998244353, G = 3, invG = 332748118;
    il int ksm(int x, int r){
        int ans = 1;
        for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
        return ans;
    }
    il poly get(int n){return poly(n + 1);}
    il void NTT (poly &a, int n, int typ){
        for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
        for (int len = 1; len < n; len <<= 1){
            int wn = ksm(typ == 1 ? G : invG, (P - 1) / (len << 1));
            for (int i = 0; i < n; i += (len << 1)){
                int w = 1;
                for (int j = 0; j < len; j++){
                    int x = a[i + j], y = 1ll * w * a[i + j + len] % P;
                    a[i + j] = (x + y) % P, a[i + j + len] = (x - y + P) % P, w = 1ll * w * wn % P;
                }
            }
        }
        if (typ == -1){
            int inv = ksm(n, P - 2);
            for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv % P;
        }
    }
    il poly mod(poly a, int n){a.resize(n, 0);return a;}
    il poly operator *(poly a, poly b){
        int n = a.size() - 1, m = b.size() - 1, L = 1;
        while (L <= n + m) L <<= 1;
        a.resize(L), b.resize(L);
        for (int i = 0; i < L; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (L >> 1) : 0);
        NTT(a, L, 1), NTT(b, L, 1);
        int inv = ksm(L, P - 2);
        for (int i = 0; i < L; i++) a[i] = 1ll * a[i] * b[i] % P;
        NTT(a, L, -1);
        return mod(a, n + m + 1);
    }
};
using namespace Poly;
int n, m, T, tu[15], tv[15];
poly f[15], p[15], h, t;
void solve(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    solve(l, mid);
    for (int i = 1; i <= m; i++){
        int u = tu[i], v = tv[i];
        h = get(mid - l), t = get(r - l);
        for (int j = l; j <= mid; j++) h[j - l] = f[v][j];
        for (int j = 0; j <= r - l; j++) t[j] = p[i][j];
        h = h * t;
        for (int j = mid + 1; j <= r; j++) f[u][j] = (f[u][j] + h[j - l]) % P;
        swap(u, v);
        h = get(mid - l), t = get(r - l);
        for (int j = l; j <= mid; j++) h[j - l] = f[v][j];
        for (int j = 0; j <= r - l; j++) t[j] = p[i][j];
        h = h * t;
        for (int j = mid + 1; j <= r; j++) f[u][j] = (f[u][j] + h[j - l]) % P;
    }
    solve(mid + 1, r);
}
signed main(){
    n = rd(), m = rd(), T = rd();
    for (int i = 1; i <= m; i++){
        tu[i] = rd(), tv[i] = rd(), p[i] = get(T);
        for (int j = 1; j <= T; j++) p[i][j] = rd();
    }
    for (int i = 1; i <= n; i++) f[i] = get(T);
    f[1][0] = 1;
    solve(0, T);
    printf ("%d\n", f[1][T]);
    return 0;
}