← 返回题目列表

AtCoder · arc129_f

F. 来玩标签吧

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

分数: 1000 点

问题陈述

潜伏和 N+M 孩子们站在数轴上。

时间 0,它们位于以下位置。

  • Snuke 已到达坐标 0.
  • N 孩子们处于负坐标。的 i- 第一个位于坐标处 -L_i.
  • M 孩子们位于正坐标。的 i- 第一个位于坐标处 R_i.

他们现在将玩捉人游戏。 具体来说,他们将采取以下行动。

  • Snuke 首先选择一个字符串 s 组成 N L和 M Rs。 然后,对于每个 i=1,2,\cdots,N+M,他执行以下操作。
    • 如果 i- 第一个字符 s is L,开始以以下速度移动 2 负方向。
    • 如果 i- 第一个字符 s is R,开始以以下速度移动 2 正方向。
    • 当抓住一个孩子(通过占据相同的坐标)时,转到下一个 i,或者结束游戏,如果 i=N+M.
  • 每个孩子都以以下速度移动 1 远离Snuke的方向。

假设我们已经找到了每个游戏结束的时间 Snuke一开始可以选择的 s 。求所有这些值的总和,取模 998244353.

约束

  • 3 \leq N,M \leq 250000
  • 1 \leq L_1 < L_2 < \cdots < L_N < 998244353
  • 1 \leq R_1 < R_2 < \cdots < R_M < 998244353
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 L_2 \cdots L_N
R_1 R_2 \cdots R_M

输出

打印答案。


示例输入 1

3 3
1 2 3
1 2 3

示例输出 1

2748

例如,如果 牌匾上写着 s=LRRLLR,游戏进行如下。

  • 时间 0: Snuke 开始向负方向移动。
  • 时间 1: Snuke 在坐标处抓住了一个孩子 -2 并开始朝正方向移动。
  • 时间 5: Snuke 在坐标处抓住了一个孩子 6 并开始朝正方向移动。
  • 时间 6: Snuke 在坐标处抓住了一个孩子 8 并开始向负方向移动。
  • 时间 22: Snuke 在坐标处抓住了一个孩子 -24 并开始向负方向移动。
  • 时间 23: Snuke 在坐标处抓住了一个孩子 -26 并开始朝正方向移动。
  • 时间 75: Snuke 在坐标处抓住了一个孩子 78 并结束游戏。

示例输入 2

7 5
89789743 196247866 205535557 542612813 782887985 889864096 899373580
539329402 618885430 714090971 717251433 860233092

示例输出 2

937403116