Sugoroku

AtCoder

IDfps_24_j

Time2000ms

Memory256MB

Difficulty—

There is a board game with $N+1$ squares numbered $0, 1, \dots, N$. You also have an $M$\-sided die, where each side shows a distinct positive integer $A_1, A_2, \dots, A_M$ with equal probability. Additionally, there are traps on squares $B_1, B_2, \dots, B_L$. Here, $1 \leq B_i \leq N-1$, and all $B_i$ are distinct. You will play the following game: * Place your piece on square $0$ at the beginning. While the game continues, repeat: * Roll the die. If your piece is on square $x$ and the die shows $y$, move the piece to square $\min(N, x+y)$. * If the piece lands on a trap square, you lose immediately. * If the piece reaches square $N$ without landing on a trap, you win immediately. Compute the probability that you win the game, modulo $998244353$. What does probability modulo $998244353$ mean? It can be proven that the probability is always a rational number. Under the constraints of this problem, if the probability is written as $\tfrac{P}{Q}$ with coprime integers $P$ and $Q$, then there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}$ and $0 \leq R < 998244353$. You are asked to compute this $R$. ## Constraints * $2 \leq N \leq 2.5 \times 10^5$ * $1 \leq M \leq N$ * $1 \leq L \leq N-1$ * $1 \leq A_1 < A_2 < \dots < A_M \leq N$ * $1 \leq B_1 < B_2 < \dots < B_L \leq N-1$ * All input values are integers ## Input The input is given from standard input in the following format: $N$ $M$ $L$ $A_1$ $A_2$ $\dots$ $A_M$ $B_1$ $B_2$ $\dots$ $B_L$ [samples]

Samples

Input #1

2 2 1
1 2
1

Output #1

499122177

You can only win if the die shows $2$. Thus, the probability is $\tfrac{1}{2}$.

Input #2

250000 10 8
1 2 3 4 5 6 7 8 9 100000
21994 47718 98917 104184 160670 204838 205220 207793

Output #2

718440495

API Response (JSON)

{
  "problem": {
    "name": "Sugoroku",
    "description": {
      "content": "There is a board game with $N+1$ squares numbered $0, 1, \\dots, N$.   You also have an $M$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_M$ with equal probability. ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_j"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a board game with $N+1$ squares numbered $0, 1, \\dots, N$.  \nYou also have an $M$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_M$ with equal probability. ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments