← 返回题单

题单练习概率与期望DP

← 上一题下一题 →

A7143 | $游走$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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$$\le 10$无$2$$3,4,5$$\le 15$$\le 100$无$2$$6,7,8$$\le 100$$\le 10^3$无$2$$9,10$$\le 10^3$$\le 10^4$无$2$$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$有向树$10$$18$$\le 10^3$$=n-1$有向树$10$$19$$\le 10^4$$=n-1$有向树$10$$20$$\le 10^5$$=n-1$有向树$10$ 其中，“有向树”的定义是：若把图视为无向图，则为一棵树（如样例 $1,2$）。 保证所有数据均按照某种方式随机，这意味着你可以认为算法执行过程中，你可以放心执行模意义下除法操作而不用担心除以零。

C++ 编辑器

输入

输出