题解 P6835 【[Cnoi2020] 线形生物】

· · 题解

前言

这道题实际上不需要复杂的数学推导，只需要利用期望的线性性就能轻松推出答案。

分析

设 E_{x\to y}\left(1\le x\le y\le n+1\right) 表示从 x 号台阶到 y 号台阶的期望步数，设 S 表示返祖边集，设 k_x 表示从 x 号台阶出发的返祖边数。根据题意以及期望的定义，有

E_{x\to x+1}=\frac{1}{k_x+1}\cdot1+\frac{1}{k_x+1}\sum_{\left(x,y\right)\in S}\left(E_{y\to x+1}+1\right).

期望具有线性性，于是对于任意 1\le x\le y\le n+1 有

E_{1\to x}+E_{x\to y}=E_{1\to y}.

二者结合，可以得到

\begin{aligned} E_{x\to x+1}&=\frac{1}{k_x+1}\cdot1+\frac{1}{k_x+1}\sum_{\left(x,y\right)\in S}\left(E_{1\to x}+E_{x\to x+1}-E_{1\to y}+1\right)\\ &=\frac{1}{k_x+1}\cdot1+\frac{1}{k_x+1}\sum_{\left(x,y\right)\in S}\left(E_{1\to x}-E_{1\to y}+1\right)+\frac{k_x}{k_x+1}E_{x\to x+1}. \end{aligned}

移项化简得

E_{x\to x+1}=1+\sum_{\left(x,y\right)\in S}\left(E_{1\to x}-E_{1\to y}+1\right).

再次根据期望的线性性有

E_{1\to x+1}=E_{1\to x}+1+\sum_{\left(x,y\right)\in S}\left(E_{1\to x}-E_{1\to y}+1\right).

有明显初始状态 E_{1\to1}=0，所以直接递推 E_{1\to x} 即可，答案即为 E_{1\to n+1}。这个算法的时空复杂度均为 \mathcal O\left(n+m\right)。

参考代码

#include <cstdio>

int read() {
  static int ch, x;
  while ((ch = getchar()) < 48) {}
  x = ch ^ 48;
  while ((ch = getchar()) >= 48) x = (((x << 2) + x) << 1) + (ch ^ 48);
  return x;
}

#define MAXN 1000010
const int P = 998244353;

// e[x] 表示文中的 E_{1 \to x}。
int e[MAXN], head[MAXN], nxt[MAXN], to[MAXN];

int main() {
  read();
  const int n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    const int x = read(), y = read();
    nxt[i] = head[x];
    to[i] = y;
    head[x] = i;
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    e[i] = ans;
    long long d = 0;
    // 注意不能直接累加 ans，因为可能出现 x = y 的情况。
    for (int j = head[i]; j; j = nxt[j]) d += ans - e[to[j]] + 1;
    ans = (ans + 1 + d) % P;
  }
  printf("%d\n", ans + (ans >> 31 & P));
  return 0;
}