A7140 | [Cnoi2020] 线形生物
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
## 题目背景
> 为了能够在冥界过上这种愉快的生活而不是被判入地狱，人类们摒弃了自行结束生命的做法，拼尽全力地生活着。如此看来，人类似乎也显得有些积极与可爱了呢。 （射命丸 文）
线形生物沿着一维的阶梯向着冥界单向地前行着。
照这样的话，它只需要一级一级地，走 $n$ 步就能够到达白玉楼。
但 Cirno 觉得这样太单调了，于是，一维的壁垒被打破，链状的道路生出了花椰菜状的枝桠。
## 题目描述
线形生物要从 $1$ 号台阶走到 $n+1$ 号台阶。
最开始，$1,2,3,\ldots,n$ 号台阶都有一条连向下一台阶的有向边 $i\rightarrow i+1$。
之后 Cirno 加入了 $m$ 条**返祖边** $u_i \rightarrow v_i (u_i \ge v_i)$，它们构成了一个**返祖图**。
线形生物每步会 **等概率地** 选取当前台阶的一条出边并走向对应的台阶。
当走到 $n+1$ 号台阶时，线形生物就会停止行走。
同时，Cirno 会统计线性生物总共走的步数，记作 $\delta$。
Cirno 想知道 $E(\delta)$（即 $\delta$ 的**数学期望**）对 $998244353$ 取模后的结果。
> 为了能够在冥界过上这种愉快的生活而不是被判入地狱，人类们摒弃了自行结束生命的做法，拼尽全力地生活着。如此看来，人类似乎也显得有些积极与可爱了呢。 （射命丸 文）
线形生物沿着一维的阶梯向着冥界单向地前行着。
照这样的话，它只需要一级一级地，走 $n$ 步就能够到达白玉楼。
但 Cirno 觉得这样太单调了，于是，一维的壁垒被打破，链状的道路生出了花椰菜状的枝桠。
## 题目描述
线形生物要从 $1$ 号台阶走到 $n+1$ 号台阶。
最开始，$1,2,3,\ldots,n$ 号台阶都有一条连向下一台阶的有向边 $i\rightarrow i+1$。
之后 Cirno 加入了 $m$ 条**返祖边** $u_i \rightarrow v_i (u_i \ge v_i)$，它们构成了一个**返祖图**。
线形生物每步会 **等概率地** 选取当前台阶的一条出边并走向对应的台阶。
当走到 $n+1$ 号台阶时，线形生物就会停止行走。
同时，Cirno 会统计线性生物总共走的步数，记作 $\delta$。
Cirno 想知道 $E(\delta)$（即 $\delta$ 的**数学期望**）对 $998244353$ 取模后的结果。
输入格式
第一行三个整数 $id$，$n$，$m$。
以下 $m$ 行，每行两个整数 $u_i$，$v_i$。
$id$ 表示 subtask 编号，其它字母含义同上文。
以下 $m$ 行，每行两个整数 $u_i$，$v_i$。
$id$ 表示 subtask 编号，其它字母含义同上文。
输出格式
一行，一个整数 $E(\delta)$，字母含义同上文。
输入输出样例
输入 #1
1 5 5 1 1 2 2 3 3 4 4 5 5
输出 #1
10
输入 #2
2 5 5 1 1 2 1 3 2 4 3 5 4
输出 #2
30
输入 #3
3 5 5 1 1 2 1 3 1 4 1 5 1
输出 #3
62
输入 #4
4 5 5 1 1 3 1 4 2 5 1 5 5
输出 #4
35
## 后置数学知识
- **可能用到的幂级数求和** : 若 $x>1$，则有 $\sum\limits_{i=1}^{\infty}\big(\frac{1}{x}\big)^i=\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}+\cdots=\frac{1}{x-1}$。
- **数学期望** : 随机试验中每次可能结果的概率乘以其结果的总和，反映随机变量平均取值的大小。
- **离散期望公式** : $E(x)=\sum\limits_{k=1}^{\infty}x_kp_k$。
## 数据范围与约定
对于 $100\%$ 的数据，保证：$id \in \{1,2,3,4,5\}$，$0 < n,m \le 10^6$，$1 \le v_i \le u_i \le n$。
#### 子任务「本题采用捆绑测试」
- Subtask1（$10\%$）: 返祖图中所有点都有自环且所有边均为自环(未画出)，总图形如 :
- Subtask2（$10\%$）: 返祖图中所有点均向且仅向自己的前驱连边，特别地，$1$ 号节点的前驱是 $1$ 号节点，总图形如 :
- Subtask3（$10\%$）: 返祖图中所有点均向且仅向 $1$ 号节点连边，总图形如 :
- Subtask4（$10\%$）: $n \le 100$，$m \le 1000$。
- Subtask5（$60\%$）: 无特殊限制。
- **可能用到的幂级数求和** : 若 $x>1$，则有 $\sum\limits_{i=1}^{\infty}\big(\frac{1}{x}\big)^i=\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}+\cdots=\frac{1}{x-1}$。
- **数学期望** : 随机试验中每次可能结果的概率乘以其结果的总和，反映随机变量平均取值的大小。
- **离散期望公式** : $E(x)=\sum\limits_{k=1}^{\infty}x_kp_k$。
## 数据范围与约定
对于 $100\%$ 的数据，保证：$id \in \{1,2,3,4,5\}$，$0 < n,m \le 10^6$，$1 \le v_i \le u_i \le n$。
#### 子任务「本题采用捆绑测试」
- Subtask1（$10\%$）: 返祖图中所有点都有自环且所有边均为自环(未画出)，总图形如 :
- Subtask2（$10\%$）: 返祖图中所有点均向且仅向自己的前驱连边，特别地，$1$ 号节点的前驱是 $1$ 号节点，总图形如 :
- Subtask3（$10\%$）: 返祖图中所有点均向且仅向 $1$ 号节点连边，总图形如 :
- Subtask4（$10\%$）: $n \le 100$，$m \le 1000$。
- Subtask5（$60\%$）: 无特殊限制。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？