← 返回题目列表

AtCoder · fps_24_j

J. 双六

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

分数: 4 点

问题陈述

有一款棋盘游戏 N+1 编号的方块 0, 1, \dots, N.
你还有一个 M双面骰子,每面显示一个不同的正整数 A_1, A_2, \dots, A_M 具有相同的概率。
此外,方格上还有陷阱 B_1, B_2, \dots, B_L。在这里, 1 \leq B_i \leq N-1,以及所有 B_i 是不同的。

您将玩以下游戏:

  • 将你的棋子放在正方形上 0 开头。当游戏继续进行时,重复:
    • 掷骰子。如果你的棋子在正方形上 x 和骰子显示 y,将棋子移至正方形 \min(N, x+y).
  • 如果棋子落在陷阱方块上,你会立即失败。
  • 如果棋子达到正方形 N 没有落在陷阱上,你立即获胜。

计算你赢得比赛的概率,取模 998244353.

概率模是什么 998244353 是什么意思? 可以证明概率总是有理数。 在这个问题的约束下,如果概率写成 \tfrac{P}{Q} 与互质整数 P 和 Q, 那么存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R < 998244353。 你被要求计算这个 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 < A_2 < \dots < A_M \leq N
  • 1 \leq B_1 < B_2 < \dots < B_L \leq N-1
  • 所有输入值均为整数

输入

输入由标准输入给出,格式如下:

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

输出

打印你赢得比赛的概率,取模 998244353.


示例输入 1

2 2 1
1 2
1

示例输出 1

499122177

只有骰子显示时您才能获胜 2。因此,概率为 \tfrac{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