分数: 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