题解 P6154 【游走】

Hexarhy · 2020-10-03 01:48:50 · 题解

Preface

蛮水的一道图论题，可以简单复习拓扑排序。

Solution

先考虑期望怎么算。显然，答案为 \dfrac{L}{S}，其中 L 为所有路径总长度，S 为路径条数。

接下来就是图论的活。

考虑到 DAG，我们可以拓扑排序后进行 dp。设 f_i 为以节点 i 为终点的路径总长度，g_i 为以节点 i 为终点的路径条数。显然，

很好理解，即 j 到 i 有边时，f_i 为所有以 j 为结尾的路径长度上均加上 1。而这样的路径有 g_j 条，所以总的就是 f_j+g_j。

至于边界值，显然 \forall i\in G,g_i=1，因为每个点的路径条数至少为 1。

那么答案为：

然后求逆元取个模就可以了。

Notice

• 注意开long long。

然后就没啥坑点了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN=1e5+5;
const ll MOD=998244353;
int n,m;
ll L,S;
vector<int> edge[MAXN];
ll f[MAXN],g[MAXN];
int indeg[MAXN];
bool visit[MAXN];

void topo_sort(void)//模板
{
    queue<int> q;
    for(int i=1;i<=n;i++)
     if(!indeg[i])
      q.push(i);
    while(!q.empty())
    {
        const int u=q.front();
        q.pop();
        if(visit[u])    continue;
        visit[u]=true;
        for(auto v:edge[u])
        {
            indeg[v]--;
            if(!indeg[v])   q.push(v);
            f[v]=(f[v]+f[u]+g[u])%MOD;//dp
            g[v]=(g[v]+g[u])%MOD;
        }
    }
}

ll qpow(ll base,ll k)//快速幂求逆元
{
    ll res=1;
    while(k)
    {
        if(k&1) res=res*base%MOD;
        base=base*base%MOD;
        k>>=1;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        edge[u].push_back(v);
        indeg[v]++;
    }
    for(int i=1;i<=n;i++)   g[i]=1;//初始化
    topo_sort();
    for(int i=1;i<=n;i++)   L=(L+f[i])%MOD;//统计答案
    for(int i=1;i<=n;i++)   S=(S+g[i])%MOD;
    cout<<(L*qpow(S,MOD-2))%MOD<<endl;
    return 0;
}