L. 旅行的意义

Codeforces

IDCF10217L

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

为什么有人永远渴望旅行，或许就因为，巧合和温暖会在下一秒蜂拥而至吧。一直想去旅游的天天决定在即将到来的五一假期中安排一场环游世界的旅行。为此，他已经提前查阅了很多资料，并准备画一张旅游路线图。天天先将所有可能会去的 $n$ 个旅游城市依次编号标记为 $1, 2, \\\\cdots, n$。如果从城市 $A$ 到城市 $B$ 有一条直达的铁路线路，他就会在图上画上一条从 $A$ 向 $B$ 的有向线段。因为天天不喜欢把时间浪费在往返的乘车上，因此他设计的旅游地图路线是一个*有向无环图*。天天身在 $1$ 号城市，他每到达一个旅游城市都会先花一天的时间游玩当地的旅游景点。接下来他也没有明确的目的地，所以第二天他会*随机地*选择该城市的一条直达线路，花费一天的时间通往下一个旅游城市。当然，如果这个城市的旅游景点太好玩的话，他可能会选择再逗留一天，但是由于假期有限，他在当前的旅游城市最多只能呆 $2$ 天。例如，当天天在城市 $C$ 时，若城市 $C$ 有 $2$ 条直达线路分别通往城市 $A$ 和城市 $B$，则在第一天的游玩过后，第二天他有 $frac(1, 3)$ 的可能会选择继续逗留在城市 $C$ 多游玩一天，但是第三天他一定不会再逗留在城市 $C$ 了；同时他有 $frac(1, 3)$ 可能会选择立即搭乘直达城市 $A$ 的高铁；他也有 $frac(1, 3)$ 的可能会选择立即搭乘直达城市 $B$ 的高铁。当天天把所有的旅游城市都游玩过后，他也就只能结束这段难忘的五一旅行假期了。现在请聪明的你帮天天提前计算一下，他本次旅行时间的期望是多少呢？容易证明天天旅行时间的期望为 $frac(P, Q)$ 的形式，其中 $P$ 和 $Q$ 互质，且 $Q not equiv 0 " "(texttt(m o d) " "998244353)$。因此答案请以 $P dot.op Q^(-1) " "(texttt(m o d) " "998244353)$ 的形式输出，其中 $Q^(-1)$ 表示 $Q$ 在取模 $998244353$ 下的逆元。第一行输入一个正整数 $T " "(1 <= T <= 10)$，表示数据组数。接下来 $T$ 组数据，每组数据均满足：对于每组数据，请输出一个非负整数，表示天天旅行时间的期望，注意换行。第一组样例只有一个旅游城市。首先，天天会在该城市游玩一天，第二天只剩下一个选择——留下来接着玩一天，再之后他就只能结束旅程了，所以旅游时间的期望是 $2$。第二组样例由两个旅游城市，从城市 $1$ 到城市 $2$ 有一条直达的线路。天天首先在城市 $1$ 游玩一天，然后有 $frac(1, 2)$ 的概率前往城市 $2$，这将花费 $1$ 天时间乘坐高铁；当然天天也有 $frac(1, 2)$ 的概率逗留在城市 $1$ 多玩一天，第三天再乘坐高铁前往城市 $2$。因此刚到达城市 $2$ 时，天天花费的旅行时间期望是 $1 + [ frac(1, 2) dot.op 1 + frac(1, 2) dot.op (1 + 1) ] = 2. 5$ 天。接着天天会在城市 $2$ 先游玩一天，但是接下来他没有其他城市可以去了，只能选择继续逗留一天然后终止旅程，容易算出本次旅程总的时间期望为 $4. 5$ 天，即 $frac(9, 2) = 9 dot.op 2^(-1) " "(texttt(m o d) " "998244353) = 499122181$。 ## Input 第一行输入一个正整数 $T " "(1 <= T <= 10)$，表示数据组数。接下来 $T$ 组数据，每组数据均满足：第一行输入两个非负整数 $n " "(1 <= n <= 10^5)$ 和 $m " "(0 <= m <= 10^5)$，分别表示天天可能旅行的城市数量 $n$ 和它们之间的直达线路数量 $m$。接下来 $m$ 行，每行输入两个正整数 $u$ 和 $v " "(1 <= u, v <= n)$，表示从城市 $u$ 到 $v$ 有一条单向直达线路，保证两个旅游城市之间最多只有 $1$ 条直达线路。 ## Output 对于每组数据，请输出一个非负整数，表示天天旅行时间的期望，注意换行。 [samples] ## Note 第一组样例只有一个旅游城市。首先，天天会在该城市游玩一天，第二天只剩下一个选择——留下来接着玩一天，再之后他就只能结束旅程了，所以旅游时间的期望是 $2$。第二组样例由两个旅游城市，从城市 $1$ 到城市 $2$ 有一条直达的线路。天天首先在城市 $1$ 游玩一天，然后有 $frac(1, 2)$ 的概率前往城市 $2$，这将花费 $1$ 天时间乘坐高铁；当然天天也有 $frac(1, 2)$ 的概率逗留在城市 $1$ 多玩一天，第三天再乘坐高铁前往城市 $2$。因此刚到达城市 $2$ 时，天天花费的旅行时间期望是 $1 + [ frac(1, 2) dot.op 1 + frac(1, 2) dot.op (1 + 1) ] = 2. 5$ 天。接着天天会在城市 $2$ 先游玩一天，但是接下来他没有其他城市可以去了，只能选择继续逗留一天然后终止旅程，容易算出本次旅程总的时间期望为 $4. 5$ 天，即 $frac(9, 2) = 9 dot.op 2^(-1) " "(texttt(m o d) " "998244353) = 499122181$。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of cities, labeled $ 1 $ to $ n $. Let $ G = (V, E) $ be a directed acyclic graph (DAG) with $ V = \{1, 2, \dots, n\} $, where each edge $ (u, v) \in E $ denotes a direct rail from city $ u $ to city $ v $. Let $ d_u = \text{out-degree of city } u $, i.e., the number of outgoing edges from city $ u $. For each city $ u $, at the end of the first day of visit, the traveler chooses: - To stay one more day (with probability $ \frac{1}{d_u + 1} $), - Or to traverse one of the $ d_u $ outgoing edges (each with probability $ \frac{1}{d_u + 1} $). After staying an extra day, the traveler must leave on the next day (no second stay). The traveler starts at city $ 1 $, and the journey ends when no unvisited city remains reachable — but since the graph is a DAG and the traveler must eventually stop when no outgoing edges remain, the process terminates when the traveler reaches a sink node and completes its two-day stay. **Constraints** 1. $ 1 \leq T \leq 10 $ 2. $ 1 \leq n \leq 10^5 $ 3. $ G $ is a DAG with no self-loops. 4. For each city $ u $, if $ d_u = 0 $, then the traveler stays exactly 2 days (one initial, one forced). 5. For each city $ u $ with $ d_u > 0 $, the traveler spends at least 1 day, and at most 2 days. **Objective** Let $ E[u] $ denote the expected total remaining travel time starting from city $ u $, including the current day’s visit. Then: - If $ d_u = 0 $: $$ E[u] = 2 $$ - If $ d_u > 0 $: $$ E[u] = 1 + \frac{1}{d_u + 1} \cdot \left( E[u] + \sum_{v \in \text{out}(u)} E[v] \right) $$ Rearranged: $$ E[u] = \frac{1 + \frac{1}{d_u + 1} \sum_{v \in \text{out}(u)} E[v]}{1 - \frac{1}{d_u + 1}} = \frac{1 + \frac{1}{d_u + 1} \sum_{v \in \text{out}(u)} E[v]}{\frac{d_u}{d_u + 1}} = \frac{d_u + 1}{d_u} + \frac{1}{d_u} \sum_{v \in \text{out}(u)} E[v] $$ Thus: $$ E[u] = 1 + \frac{1}{d_u} \left(1 + \sum_{v \in \text{out}(u)} E[v] \right) $$ Compute $ E[u] $ for all $ u $ in reverse topological order. Answer is $ E[1] \mod 998244353 $.

API Response (JSON)

{
  "problem": {
    "name": "L. 旅行的意义",
    "description": {
      "content": "为什么有人永远渴望旅行，或许就因为，巧合和温暖会在下一秒蜂拥而至吧。 一直想去旅游的天天决定在即将到来的五一假期中安排一场环游世界的旅行。为此，他已经提前查阅了很多资料，并准备画一张旅游路线图。天天先将所有可能会去的 $n$ 个旅游城市依次编号标记为 $1, 2, \\\\\\\\cdots, n$。如果从城市 $A$ 到城市 $B$ 有一条直达的铁路线路，他就会在图上画上一条从 $A$ 向 $B$ 的",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10217L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "为什么有人永远渴望旅行，或许就因为，巧合和温暖会在下一秒蜂拥而至吧。\n\n一直想去旅游的天天决定在即将到来的五一假期中安排一场环游世界的旅行。为此，他已经提前查阅了很多资料，并准备画一张旅游路线图。天天先将所有可能会去的 $n$ 个旅游城市依次编号标记为 $1, 2, \\\\\\\\cdots, n$。如果从城市 $A$ 到城市 $B$ 有一条直达的铁路线路，他就会在图上画上一条从 $A$ 向 $B$ 的...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities, labeled $ 1 $ to $ n $.  \nLet $ G = (V, E) $ be a directed acyclic graph (DAG) with $ V = \\{1, 2, \\dots, n\\} $, where each edge $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments