ID: 8612

传统题

1000ms

128MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

admin

标签>

P6154

概率与期望

拓扑排序

动态规划

CSP-S

有向无环图随机游走(Random Walk on DAG)

题目描述

zbw 在 B 城游走。

B 城可以看作一个有 $n$ 个点 $m$ 条边的有向无环图。可能存在重边。

zbw 在 B 城随机游走，他会在所有路径中随机选择一条路径，选择所有路径的概率相等。路径的起点和终点可以相同。

定义一条路径的长度为经过的边数，你需要求出 zbw 走的路径长度的期望，答案对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $x,y$ ，表示存在一条从 $x$ 到 $y$ 的有向边。

输出格式

一行一个整数，表示答案对 $998244353$ 取模后的值。

样例输入 #1

3 2
1 2
3 2

样例输出 #1

199648871

样例输入 #2

样例输出 #2

630470119

样例输入 #3

样例输出 #3

887328315

数据范围

样例说明：样例的答案分别为 $\dfrac{2}{5}$ ， $\dfrac{25}{19}$ 和 $\dfrac{11}{9}$ 。

测试点编号	$n$	$m$	特殊性质	每测试点分数
$1,2$	$\le 10$		无	$2$
$3,4,5$	$\le 15$	$\le 100$
$6,7,8$	$\le 100$	$\le 10^3$
$9,10$	$\le 10^3$	$\le 10^4$
$11,12$	$\le 10^4$	$\le 10^5$		$5$
$13,14$	$\le 10^5$	$\le 2\times10^5$		$5$
$15,16$	$\le 10^5$	$\le 7\times10^5$		$10$
$17$	$\le 10$	$=n-1$	有向树
$18$	$\le 10^3$
$19$	$\le 10^4$
$20$	$\le 10^5$

其中，“有向树”的定义是：若把图视为无向图，则为一棵树（如样例 $1,2$ ）。

保证所有数据均按照某种方式随机，这意味着你可以认为算法执行过程中，你可以放心执行模意义下除法操作而不用担心除以零。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

Subtask	分值	测试点编号	说明
0	15	1~3	样例
1	25	4~9	小规模 n≤100, m≤1000 / 特殊: 有向树
2	30	10~17	中等规模 n≤10000, m≤100000
3	30	18~25	满规模 n=100000, m=500000 极限 DAG DP 测试

出处：原题链接

#P6154. 有向无环图随机游走(Random Walk on DAG)

有向无环图随机游走(Random Walk on DAG)

有向无环图随机游走(Random Walk on DAG)

题目描述

输入格式

输出格式

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

样例输入 #3

样例输出 #3

数据范围

知识点与难度

测试点分布

登录