分数: 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.