Between Two Arrays

题目描述

一个由 $n$ 个数构成的序列 $S = (s_1, s_2, \dots, s_n)$ 当且仅当对每个 $i$ $(1 \leq i \leq n - 1)$ 都满足 $s_i \leq s_{i+1}$ 时，被称为非递减。 给出两个长度为 $N$ 的非递减整数序列：$A = (a_1, a_2, \dots, a_N)$ 和 $B = (b_1, b_2, \dots, b_N)$。
考虑一个满足下列条件的长度为 $N$ 的非递减整数序列 $C = (c_1, c_2, \dots, c_N)$：

$a_i \leq c_i \leq b_i$ 对于每个 $i$ $(1 \leq i \leq N)$ 成立。

求可以作为 $C$ 的序列的个数，对 $998244353$ 取模。

输入格式

输入按如下格式由标准输入提供： $N$ $a_1$ $a_2$ $\dots$ $a_N$ $b_1$ $b_2$ $\dots$ $b_N$

输出格式

输出可以作为 $C$ 的序列的个数，对 $998244353$ 取模。

2
1 1
2 3

5

3
2 2 2
2 2 2

1

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

978222082

提示

$1 \leq N \leq 3000$ $0 \leq a_i \leq b_i \leq 3000$ $(1 \leq i \leq N)$ 序列 $A$ 和 $B$ 是非递减的。 输入中的所有数值均为整数。可以作为 $C$ 的序列共有五个，如下所示。

$(1, 1)$ $(1, 2)$ $(1, 3)$ $(2, 2)$ $(2, 3)$

注意 $(2, 1)$ 不满足条件，因为它不是非递减的。
可以作为 $C$ 的序列共有一个，如下所示。

$(2, 2, 2)$
请注意对 $998244353$ 取模。

标签: AtCoder|abc222D

来源

AtCoder|abc222D