P6154 游走

与绿豆蛙归宿这道题不同的是 每个点都可以是起点和终点 并且允许从自己走到自己 细节需要处理好

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 5;
const int MOD = 998244353;
int n, m;
int f[N], g[N]; // f表示路径长度和 g表示路径数
vector<int> e[N];
inline int QP(int a, int b, int p)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans;
}
inline int inv(int x)
{
    return QP(x, MOD - 2, MOD);
}
void dfs(int now)
{
    if (g[now])
        return;
    g[now] = 1; // 初始每个点的路径条数都是1 这条路的长度为0 (自己走向自己)
    for (auto i : e[now])
    {
        dfs(i);
        g[now] = (g[now] + g[i]) % MOD;        // 更新这个点的路径条数
        f[now] = (f[now] + f[i] + g[i]) % MOD; // 当前这个点的长度和需要加上下一个点的长度和并且将下个点的每条边长度加1
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!g[i])
            dfs(i); // 不知道起点终点 没有保证图是连通的 应当扫一遍都尝试搜
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        sum = (sum + f[i]) % MOD, cnt = (cnt + g[i]) % MOD;
    // 期望 = 总路径长度和 / 总路径条数
    cout << sum * inv(cnt) % MOD << endl;
    // 题目要求给分数取模
}