J - スゴロク 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 4 点

問題文

マス 0, マス 1, \dots, マス N の N+1 個のマスからなるスゴロクがあります。
また、正整数 A_1, A_2, \dots, A_M が等確率で出る M 面サイコロがあります。ここで A_1, A_2, \dots, A_M は相異なります。
また、マス B_1, マス B_2, \dots, マス B_L には落とし穴があります。ここで 1 \leq B_i \leq N-1 が成り立ち、また B_1, B_2, \dots, B_L は相異なります。
あなたはこのスゴロクを使ってゲームをします。ゲームの手順は次の通りです：

  • はじめに駒をマス 0 に置く。そして、ゲームが続いている間、次の操作を行う。
    • サイコロを振る。駒があるマスを x、サイコロで出た整数を y として駒をマス \min(N, x+y) に動かす。
  • 操作によって落とし穴があるマスに駒を動かした場合はあなたは負けとなり、ゲームを終了する。
  • 落とし穴に駒を動かすことなくマス N に駒を移動できた場合はあなたは勝ちとなり、ゲームを終了する。

あなたがゲームに勝つ確率を \text{mod }998244353 で計算してください。

確率 \text{mod }998244353 とは 求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 2 \leq N \leq 2.5 \times 10^5
  • 1 \leq M \leq N
  • 1 \leq L \leq N-1
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N
  • 1 \leq B_1 \lt B_2 \lt \dots \lt B_L \leq N-1
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M L
A_1 A_2 \dots A_M
B_1 B_2 \dots B_L

出力

あなたがゲームに勝つ確率を \text{mod }998244353 で計算した時の答えを出力せよ。

入力例 1

2 2 1
1 2
1

出力例 1

499122177

サイコロで 2 が出た場合にのみあなたは勝つことができます。よって答えは \frac{1}{2} です。

入力例 2

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

出力例 2

718440495

Score: 4 points

Problem Statement

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

Output

Print the probability that you win the game, modulo 998244353.

Sample Input 1

2 2 1
1 2
1

Sample Output 1

499122177

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

Sample Input 2

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

Sample Output 2

718440495