← 返回题目列表

AtCoder · nikkei2019_2_final_f

F. 跳过 2

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

配点 : 1000 点

問題文

1 我决定将所有值添加到 N 的顺序编号 N 方块排成一条直线。其中 B_1, ..., B_K 的 K 广场内有障碍物,无法进入。

高桥君从现在开始要做弥撒。 启动 1 并 我即将前往 N 。

不过,高桥可以使用的移动方式是有限制的。1 第二步,高桥 当你在 x 您只能移动到 x + D_1, x + D_2, ..., x + D_M 中的一个方格。

有障碍物的方块, 您只能跳转到N 方格。

高桥君 1 移动到广场 x 来自质量 当移动到 y 时,满足以下条件的最小非负整数: 它的成本是 i 。

  • x + 1 以上 y 以下任意整数 不能被 2^i 整除。

重复从一个方格移动到另一个方格 来自 1 到 N 的路径的成本是每次行程的成本之和。

所有可能路线的成本总和为 除以 998244353 后求余数。

制約

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-2
  • 1 \leq M \leq N-1
  • 1 < B_1 < B_2 < \cdots < B_K < N
  • 0 < D_1 < D_2 < \cdots < D_M < N
  • 所有输入均为整数 打印除以

入力

输入将以以下形式从标准输入给出。

N K M
B_1 B_2 \cdots B_K
D_1 D_2 \cdots D_M

出力

所有可能路线的成本总和为 除以 998244353 后的余数。


入力例 1

3 1 2
2
1 2

出力例 1

2

可能的路线是 仅那些移至 1 到 3 的。

满足条件的最小非负整数为 2 可以验证如下,所以质量 移动到 1 到 3 的成本是 2 。

  • 2^1 = 2 中 由于 2 可整除,1 不满足条件。
  • 2^2 = 4 中 由于 2, 3 都不可整除,所以2 满足条件。

因此,该路线的成本为 2 。


入力例 2

4 1 3
3
1 2 3

出力例 2

8

可能的路线如下 2 有一条街。 转至

  • 质量 重复从 1 到 4 。这条路线的费用是 转到 3 。

  • 质量 重复从 1 到 2 并 2 到 4 。这条路线的费用是 转到 2 + 3 = 5 。

因此,所有路由的成本总和为 8 。


入力例 3

4 2 2
2 3
1 2

出力例 3

0

首先质量 我无法到达 4 ,所以0 。


入力例 4

10 2 4
2 7
1 2 3 9

出力例 4

301