Description

题目链接

题目大意:给定一条 $n + 1$ 个点的链满足 $i \to i + 1$,在链上添加 $m$ 条边 $u \to v$ 满足 $u \ge v$。每次等概率选取一条边走出,求从 $1$ 走到 $n$ 的步数的期望。$1 \le n, m \le 10^6$。

Solution

设 $f_i$ 表示从 $i$ 走到 $i + 1$ 的期望,则答案为 $\sum f_i$。

接下来考虑转移,设 $i$ 点的出度为 $d$,则有 $f_i = \dfrac{1}{d} + \dfrac{\sum \sum \limits_{j = v}^{i} f_j}{d}$($v$ 为 $i$ 后退到的点)。

对式子进行化简,得到 $f_i = d + \sum \sum \limits_{j = v}^{i - 1} f_j$。

时间复杂度为 $O(n + m)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

const LL mod = 998244353;

std::vector<int> g[1000010];
LL f[1000010], s[1000010];
int out[1000010];
int n, m, id;

int main() {
    read(id), read(n), read(m);
    for (int i = 1, u, v; i <= m; ++i) {
        read(u), read(v);
        g[u].push_back(v);
        ++out[u];
    }
    for (int i = 1; i <= n; ++i) {
        f[i] = out[i] + 1;
        for (auto j : g[i]) {
            f[i] += s[i - 1] - s[j - 1];
            f[i] %= mod;
        }
        s[i] = s[i - 1] + f[i];
        s[i] %= mod;
    }
    printf("%lld\n", (s[n] % mod + mod) % mod);
    return 0;
}
Last modification:November 16th, 2021 at 08:18 pm