← 返回题目列表

AtCoder · abc309_h

Ex. 简单路径计数问题

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

分数: 650 点

问题陈述

我们有一个网格 N 行和 M 列。 我们表示为 (i,j) 中的单元格 i从顶部开始的第行和 j左起第 列。

给定整数序列 A=(A_1,A_2,\dots,A_K) 和 B=(B_1,B_2,\dots,B_L) 长度 K 和 L。

求总和,取模 998244353,关于所有整数对的以下问题的答案 (i,j) 这样 1 \le i \le K 和 1 \le j \le L.

  • 一块最初放置在 (1,A_i)。 有多少条路可以到达 (N,B_j) 重复以下动作 (N-1) 次?
    • 让 (p,q) 是该作品的当前单元格。 将其移至 (p+1,q-1),(p+1,q),或 (p+1,q+1),而不将其移出网格。

约束

  • 1 \le N \le 10^9
  • 1 \le M,K,L \le 10^5
  • 1 \le A_i,B_j \le M

输入

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

N M K L
A_1 A_2 \dots A_K
B_1 B_2 \dots B_L

输出

打印答案。


示例输入 1

3 4 1 2
1
1 2

示例输出 1

4

对于 (i,j)=(1,1),以下两条路径是可能的:

  • (1,1) \rightarrow (2,1) \rightarrow (3,1)
  • (1,1) \rightarrow (2,2) \rightarrow (3,1)

对于 (i,j)=(1,2),以下两条路径是可能的:

  • (1,1) \rightarrow (2,1) \rightarrow (3,2)
  • (1,1) \rightarrow (2,2) \rightarrow (3,2)

因此,答案是 2 + 2 =4.


示例输入 2

5 8 4 5
3 1 4 1
2 7 1 8 2

示例输出 2

137

示例输入 3

883671387 87719 10 12
86879 64174 47274 41688 17713 50897 53989 7210 30894 5714
60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721

示例输出 3

941873621