← 返回题目列表

Codeforces · 1411/G

G. 没有游戏就没有生活

中文机器翻译题面 查看原题

让我们考虑以下 Alice 和 Bob 在有向无环图上的游戏。每个顶点可以包含任意数量的芯片。爱丽丝和鲍勃交替轮流。爱丽丝先走。在一回合中,玩家可以沿着从包含该筹码的顶点到该边的末端的任何边恰好移动一个筹码。不能转弯的人就输了。两名球员都发挥最佳。

考虑在具有 $$$n$$$ 个顶点的给定图上每秒发生的以下过程:

1. 从$$$[1, n + 1]$$$ 中等概率地选择一个整数$$$v$$$。
2. 如果 $$$v \leq n$$$,我们向第 $$$v$$$ 个顶点添加一个芯片,然后返回步骤 1。
3. 如果 $$$v = n + 1$$$,Alice 和 Bob 按照当前的筹码排列进行游戏,并确定获胜者。之后,该过程终止。

求 Alice 赢得比赛的概率。可以看出,答案可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是互质整数,$$$Q \not\equiv 0 \pmod{998\,244\,353}$$$。打印 $$$P \cdot Q^{-1} \bmod 998\,244\,353$$$ 的值。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ - 图的顶点和边的数量 ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$)。

以下 $$$m$$$ 行包含边缘描述。其中第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ - 第 $$$i$$$ 边的开始和结束顶点 ($$$1 \leq u_i, v_i \leq n$$$)。保证该图是非循环的。

输出

输出一个整数——爱丽丝获胜的概率以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

1 0

输出 #1

0

输入 #2

2 1
1 2

输出 #2

332748118

输入 #3

5 5
1 4
5 2
4 3
1 5
5 4

输出 #3

931694730