← 返回题目列表

Codeforces · 1366/E

E. 两个数组

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

给定两个数组 $$$a_1, a_2, \dots , a_n$$$ 和 $$$b_1, b_2, \dots , b_m$$$。数组 $$$b$$$ 按升序排序(对于每个 $$$i$$$,$$$b_i < b_{i + 1}$$$ 从 $$$1$$$ 到 $$$m - 1$$$)。

您必须将数组 $$$a$$$ 划分为 $$$m$$$ 连续子数组,以便对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,第 $$$i$$$ 个子数组的最小值等于 $$$b_i$$$。请注意,每个元素都属于一个子数组,并且它们的形成方式如下:$$$a$$$ 的前几个元素组成第一个子数组,$$$a$$$ 的接下来的几个元素组成第二个子数组,依此类推。

例如,如果 $$$a = [12, 10, 20, 20, 25, 30]$$$ 且 $$$b = [10, 20, 30]$$$ 则数组 $$$a$$$ 有两个好的分区:

1. $$$[12, 10, 20], [20, 25], [30]$$$;
2. $$$[12, 10], [20, 20, 25], [30]$$$.

你必须计算数组 $$$a$$$ 的划分方法数。由于数字可能相当大,因此打印它对 998244353 进行模运算。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 分别是数组 $$$a$$$ 和 $$$b$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots , b_m$$$ ($$$1 \le b_i \le 10^9; b_i < b_{i+1}$$$) — 数组 $$$b$$$。

输出

仅在一行中打印一个整数 — 数组 $$$a$$$ 除以 998244353 为模的方法数。

示例

输入 #1

6 3
12 10 20 20 25 30
10 20 30

输出 #1

2

输入 #2

4 2
1 3 3 7
3 7

输出 #2

0

输入 #3

8 2
1 2 2 2 2 2 2 2
1 2

输出 #3

7