/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ n の数列 S = (s_1, s_2, \dots, s_n) がすべての i (1 \leq i \leq n - 1) に対して s_i \leq s_{i+1} を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。
広義単調増加な長さ 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 で割ったあまりを求めてください。
制約
- 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
出力
C としてあり得る数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 1 1 2 3
出力例 1
5
C としてあり得る数列は次の 5 個です。
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
数列 (2, 1) は広義単調増加でないため条件を満たさないことに注意してください。
入力例 2
3 2 2 2 2 2 2
出力例 2
1
C としてあり得る数列は次の 1 個です。
- (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 で割ったあまりを求めることに注意してください。
Score : 400 points
Problem Statement
A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).
Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:
- a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).
Find the number, modulo 998244353, of sequences that can be C.
Constraints
- 1 \leq N \leq 3000
- 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
- The sequences A and B are non-decreasing.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \dots a_N b_1 b_2 \dots b_N
Output
Print the number, modulo 998244353, of sequences that can be C.
Sample Input 1
2 1 1 2 3
Sample Output 1
5
There are five sequences that can be C, as follows.
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
Note that (2, 1) does not satisfy the condition since it is not non-decreasing.
Sample Input 2
3 2 2 2 2 2 2
Sample Output 2
1
There is one sequence that can be C, as follows.
- (2, 2, 2)
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100
Sample Output 3
978222082
Be sure to find the count modulo 998244353.