AT_fps_24_j スゴロク

题目描述

有一个包含 $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$ 取模？可以证明概率一定是一个有理数。在本题的约束条件下，如果概率写作 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 互质，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。你需要计算的就是这个 $R$。

输入格式

输入从标准输入读取，格式如下：

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

输出格式

输出你获胜的概率，对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

2 2 1
1 2
1

输出 #1

499122177

输入输出样例 #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

说明/提示

样例解释 1

你只有在骰子掷出 $2$ 时才能获胜。因此概率为 $\frac{1}{2}$。

数据范围

• $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$
• 所有输入值均为整数。

由 ChatGPT 5 翻译