102223: [AtCoder]ABC222 D - Between Two Arrays

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

给定两个单调不下降的序列 $a$,$b$,求单调不下降序列 $c$ ,满足 $a_i\le c_i\le b_i$ 并且最长的数量。对 $998244353$ 取模。 $1\le n\le 3000$,$0\le a_i\le b_i\le 3000$。

Output

得分:400分

问题描述

如果满足对于所有的$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$取模。

限制条件

  • $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$的序列,如下所示。

  • $(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$取模的计数。

加入题单

上一题 下一题 算法标签: