Preparando MOJI

No Game No Life

2000ms 262144K

Description:

Let's consider the following game of Alice and Bob on a directed acyclic graph. Each vertex may contain an arbitrary number of chips. Alice and Bob make turns alternating. Alice goes first. In one turn player can move exactly one chip along any edge outgoing from the vertex that contains this chip to the end of this edge. The one who cannot make a turn loses. Both players play optimally.

Consider the following process that takes place every second on a given graph with $$$n$$$ vertices:

  1. An integer $$$v$$$ is chosen equiprobably from $$$[1, n + 1]$$$.
  2. If $$$v \leq n$$$, we add a chip to the $$$v$$$-th vertex and go back to step 1.
  3. If $$$v = n + 1$$$, Alice and Bob play the game with the current arrangement of chips and the winner is determined. After that, the process is terminated.

Find the probability that Alice will win the game. It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{998\,244\,353}$$$. Print the value of $$$P \cdot Q^{-1} \bmod 998\,244\,353$$$.

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and edges of the graph ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$).

The following $$$m$$$ lines contain edges description. The $$$i$$$-th of them contains two integers $$$u_i$$$ and $$$v_i$$$ — the beginning and the end vertices of the $$$i$$$-th edge ($$$1 \leq u_i, v_i \leq n$$$). It's guaranteed that the graph is acyclic.

Output:

Output a single integer — the probability of Alice victory modulo $$$998\,244\,353$$$.

Sample Input:

1 0

Sample Output:

0

Sample Input:

2 1
1 2

Sample Output:

332748118

Sample Input:

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

Sample Output:

931694730

Informação

Codeforces

Provedor Codeforces

Código CF1411G

Tags

bitmasksgamesmathmatrices

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:06:31

Relacionados

Nada ainda