代码求调
查看原帖
代码求调
675208
coder2009楼主2024/8/27 20:18

样例全过,交上去就WA,求好心人调试

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const ll mod = 998244353;
const int maxn = 105;
ll f[maxn][maxn][maxn], dp[maxn][maxn], p[maxn];
int head[maxn], idx = 0;
struct edge {
    ll to;
    int next;
} g[maxn];

void add(int u, ll v) {
    g[++idx].to = v;
    g[idx].next = head[u];
    head[u] = idx;
}

ll inv(ll x) {
    ll res = 1;
    ll y = mod - 2;
    while (y) {
        if (y & 1) {
            res = res * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

ll md(ll x) {
    return (x + mod) % mod;
}

void solve() {
    int n, t, m;
    cin >> n >> t >> m;
    for (int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        p[i] = inv(x);
        for (int j = 0; j < x; ++j){
            ll v;
            cin >> v;
            add(i, v);
        }
    }
    for (int i = 1; i <= n; ++i){
        f[0][i][i] = 1;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int s = 1; s <= n; ++s) {
                if (j == s) {
                    f[i][j][s] = 1;
                    continue;
                }
                f[i][j][s] = 0;
                for (int k = head[j]; k; k = g[k].next) {
                    ll v = g[k].to;
                    f[i][j][s] = md((f[i][j][s] + f[i - 1][v][s]) % mod);
                }
                f[i][j][s] = md(f[i][j][s] * p[j] % mod);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = 0;
            for (int s = head[j]; s; s = g[s].next) {
                ll v = g[s].to;
                dp[i][j] = md((dp[i][j] + dp[i - 1][v] + f[i - 1][v][j] * v % mod) % mod);
            }
            dp[i][j] = md(dp[i][j] * p[j] % mod);
        }
    }
    cout << dp[m][t];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

2024/8/27 20:18
加载中...