AT_abc222_d [ABC222D] Between Two Arrays

题目描述

当且仅当对于所有 $i$ 满足 $1 \leq i \leq n-1$ 时都有 $s_i \leq s_{i+1}$，我们称长度为 $n$ 的数列 $S = (s_1, s_2, \dots, s_n)$ 是“广义单调递增”的。

给定两个长度为 $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)$：

• 对于所有 $i$ 满足 $1 \leq i \leq N$，都有 $a_i \leq c_i \leq b_i$。

请输出作为 $C$ 可能的数列的个数对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\dots$ $a_N$ $b_1$ $b_2$ $\dots$ $b_N$

输出格式

输出作为 $C$ 可能的数列的个数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

2
1 1
2 3

输出 #1

5

输入输出样例 #2

输入 #2

3
2 2 2
2 2 2

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

978222082

说明/提示

限制条件

• $1 \leq N \leq 3000$
• $0 \leq a_i \leq b_i \leq 3000$（$1 \leq i \leq N$）
• 整数列 $A, B$ 均为广义单调递增。
• 输入均为整数。

样例解释 1

作为 $C$ 可能的数列有如下 $5$ 个：

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

注意，数列 $(2, 1)$ 不满足广义单调递增的条件，因此不计入答案。

样例解释 2

作为 $C$ 可能的数列仅有 $1$ 个：

• $(2, 2, 2)$

样例解释 3

请注意，要求输出的结果需对 $998244353$ 取模。

由 ChatGPT 4.1 翻译