← 返回题目列表

AtCoder · abc222_d

G. 两个阵列之间

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

分数: 400 点

问题陈述

一系列 n 数字, S = (s_1, s_2, \dots, s_n),据说是 非递减 当且仅当 s_i \leq s_{i+1} 对于每个都成立 i (1 \leq i \leq n - 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).

求模数 998244353,可以是 C.

约束

  • 1 \leq N \leq 3000
  • 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
  • 序列 A 和 B 不减少。
  • 输入中的所有值都是整数。

输入

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

N
a_1 a_2 \dots a_N
b_1 b_2 \dots b_N

输出

打印数字,模数 998244353,可以是 C.


示例输入 1

2
1 1
2 3

示例输出 1

5

有五个序列可以 C,如下。

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

请注意 (2, 1) 不满足条件,因为它不是非递减的。


示例输入 2

3
2 2 2
2 2 2

示例输出 2

1

有一个序列可以 C,如下。

  • (2, 2, 2)

示例输入 3

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

示例输出 3

978222082

一定要找到计数模数 998244353.