abc372-F 題解

連結

可以列出$\text{dp}_{i,j}=\sum_{u \in S}\text{dp}_{i-1,u}$，其中$S$是有邊$u \to j$的所有$u$的集合。
這樣轉移的複雜度會是$O((N+M)K)$，不會過。
觀察到題目給的圖是一個大環加一些邊，而且環以外的邊數$M$很少。
而且用大環轉移其實就是把整個陣列往右cyclic shift一位。
所以可以先轉移大環，再把$M$條額外的邊的轉移補上。

code:

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

constexpr int Mod = 998'244'353;

void mad(int& x, int y) {
    x += y - Mod;
    x += Mod & (x >> 31);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k; cin >> n >> m >> k;
    vec<int> dp_arr(n), dp_aux(m);
    int offset{};
    auto dp = [&](int i) -> int& {
        i += offset - n;
        i += n & (i >> 31);
        return dp_arr[i];
    };
    vec<pair<int, int>> edges(m);
    for (auto& [x, y] : edges) {
        cin >> x >> y;
        --x, --y;
    }
    dp_arr[0] = 1;
    for (int t = 1; t <= k; t++) {
        for (int i = 0; i < m; i++) {
            auto [x, y] = edges[i];
            dp_aux[i] = dp(x);
        }
        if (offset == 0) offset = n;
        offset -= 1;
        for (int i = 0; i < m; i++) {
            auto [x, y] = edges[i];
            mad(dp(y), dp_aux[i]);
        }
    }
    cout << reduce(ALL(dp_arr), 0LL) % Mod << '\n';
}