洛谷P6154 游走 题解
题目链接：P6154 游走
题意：
S 城可以看作一个有 \(n\) 个点 \(m\) 条边的有向无环图。可能存在重边。
cxy 在 S 城随机游走，她会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。
定义一条路径的长度为经过的边数，你需要求出 cxy 走的路径长度的期望，答案对 \(998244353\) 取模。
输入格式：
第一行两个整数 \(n,m\)。
接下来 \(m\) 行，每行两个整数 \(x,y\)，表示存在一条从 \(x\) 到 \(y\) 的有向边。
输出格式：
一行一个整数，表示答案对 \(998244353\) 取模后的值。
数据范围：
\(1\le n \le 10^5,~0 \le m \le 7\times 10^5\) 。
期望dp + topo 小清新题~
设 \(f_u\) 表示以 \(u\) 为终点的路径总长度，\(g_u\) 表示以 \(u\) 为终点的路径总条数。
考虑以拓扑序转移。对于边 \((u,v)\)
，有转移（其中 \(a \uparrow b + c\)
表示 a += b+c 。） \[
f_v \uparrow f_u + g_u\\
g_v \uparrow g_u
\] 第一个式子是因为 \(f_v\)
为所有以 \(u\)
为终点的路径的总长度加上一个增量。
这个增量就是 \(1\ \times\) 以 \(u\) 为终点的路径数量，也就是 \(g_u\) 。
那么答案就是 \(\frac{\sum f_u}{\sum g_u}\) ，要算个逆元。
时间复杂度 \(\mathcal{O}(n+m)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
#define inv(x) qpow((x), mod-2)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(1e5+15))
#define M ((int)(1e6+15))
queue<int> q;
int n,m,pos=1,head[N],in[N],f[N],g[N];
struct Edge{ int u,v,next; } e[M];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; ++in[v]; }
int qpow(int a,int b)
{
int ans = 1, base = a % mod;
for(; b; b >>= 1)
{
if(b & 1) ans = ans * base % mod;
base = base * base % mod;
}
return ans;
}
void topo_sort()
{
for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v; if(!(--in[v])) q.push(v);
add(f[v], (f[u] + g[u]) % mod); add(g[v], g[u]);
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); }
for(int i=1; i<=n; i++) g[i] = 1; topo_sort();
int A = 0, B = 0;
for(int i=1; i<=n; i++) { add(A, f[i]); add(B, g[i]); }
cout << A * inv(B) % mod << '\n';
return 0;
}参考文献：
