UOJ

分析

设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。

那么有
$$
f_{i, j, w} = \sum_{k = 1}^n \sum_{v} f_{i, k, v} \times g_{k, j, w - v} + [i = j \land w = 0]
$$
后面那个中括号表示不走的情况。

设 $F_{i,j}(x) = \sum_{k\geq 0} f_{i,j,k} x^k$，$G_{i,j}(x) = \sum_{k\geq 0} g_{i, j, k} x^k$，并设 $F,G$ 表示这两个生成函数构成的矩阵，则有
$$
F = F\times G + I
$$
即
$$
F = \frac{I}{I - G}
$$
可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。

然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻址优化什么的都加上去。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 8 + 5, W = 131072 + 10;
const int mod = 998244353;
int upd(const int &x) { return x + (x >> 31 & mod); }
int qpow(int a, int b) {
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) c = 1ll * c * a % mod;
    return c;
}

int r[W], w[W], ow[2][W], Lim;
void NTT(int *A, int n, int op) {
    for (int i = 0; i < n; ++i)
        if (i < r[i]) swap(A[i], A[r[i]]);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0, k = 0; j < i; ++j, k += Lim / i) w[j] = ow[op < 0][k];
        for (int j = 0; j < n; j += i << 1)
            for (int k = 0; k < i; ++k) {
                int x = A[j + k], y = 1ll * w[k] * A[j + k + i] % mod;
                A[j + k] = upd(x + y - mod), A[j + k + i] = upd(x - y);
            }
    }
    if (op == -1) {
        int inv = qpow(n, mod - 2);
        for (int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod;
    }
}
int NTT_init(int n) {
    int lim = 1, l = 0;
    for (; lim < n; lim <<= 1, ++l);
    for (int i = 0; i < lim; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    return lim;
}
void PolyInv(int *F, int *G, int n) {
    static int A[W], B[W];
    if (n == 1) { G[0] = qpow(F[0], mod - 2); return; }
    PolyInv(F, G, n >> 1);
    for (int i = 0; i < n; ++i) A[i] = F[i], B[i] = G[i];
    int lim = NTT_init(n << 1);
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i) A[i] = 1ll * A[i] * B[i] % mod * B[i] % mod;
    NTT(A, lim, -1);
    for (int i = 0; i < n; ++i) G[i] = (2ll * G[i] - A[i] + mod) % mod;
    for (int i = 0; i < lim; ++i) A[i] = B[i] = 0;
}

int n, m, Q, L;
int A[N][N << 1][W];

void MatrixInv() {
    static int F[W], G[W], H[N << 1][W];
    Lim = 1; int l = 0;
    for (; Lim <= L << 1; Lim <<= 1, ++l);
    ow[0][0] = 1, ow[0][1] = qpow(3, (mod - 1) / (Lim << 1));
    ow[1][0] = 1, ow[1][1] = qpow(ow[0][1], mod - 2);
    for (int i = 2; i < Lim; ++i) {
        ow[0][i] = 1ll * ow[0][i - 1] * ow[0][1] % mod;
        ow[1][i] = 1ll * ow[1][i - 1] * ow[1][1] % mod;
    }
    for (int i = 1; i <= n; ++i) A[i][i][0] = A[i][i + n][0] = mod - 1;
    for (int i = 1; i <= n; ++i) {
        memset(F, 0, Lim << 2);
        PolyInv(A[i][i], F, Lim >> 1);
        for (int j = 0; j < Lim; ++j) r[j] = (r[j >> 1] >> 1) | ((j & 1) << (l - 1));
        NTT(F, Lim, 1);
        for (int j = i; j <= i + n; ++j) {
            NTT(A[i][j], Lim, 1);
            for (int k = 0; k < Lim; ++k) A[i][j][k] = 1ll * A[i][j][k] * F[k] % mod;
            NTT(A[i][j], Lim, -1);
            for (int k = L + 1; k < Lim; ++k) A[i][j][k] = 0;
            memcpy(H[j], A[i][j], Lim << 2);
            NTT(H[j], Lim, 1);
        }
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            memcpy(F, A[j][i], Lim << 2);
            NTT(F, Lim, 1);
            for (int k = i + 1; k <= i + n; ++k) {
                for (int l = 0; l < Lim; ++l) G[l] = 1ll * F[l] * H[k][l] % mod;
                NTT(G, Lim, -1);
                for (int l = 0; l <= L; ++l) A[j][k][l] = upd(A[j][k][l] - G[l]);
            }
        }
    }
}

int main() {
    n = read(), m = read(), Q = read(), L = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        ++A[u][v][w];
    }
    MatrixInv();
    while (Q--) {
        int u = read(), v = read(), w = read();
        printf("%d\n", A[u][v + n][w]);
    }
    return 0;
}