Đếm dãy không giảm

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Ta định nghĩa dãy số nguyên \(\left[s_1,s_2,...,s_m\right]\) là một dãy không giảm khi và chỉ khi \(s_i\le s_{i+1}\) với mọi \(1\le i < m\).

Cho trước hai dãy không giảm \([l_1, l_2,...,l_n]\) và \([r_1, r_2,...,r_n]\), bạn hãy đếm số lượng dãy không giảm \([a_1,a_2,...,a_n]\) sao cho \(l_i\le a_i\le r_i\) với mọi \(1\le i\le n\) nhé! Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input
  • Dòng đầu chứa số nguyên \(n\) \(\left(1\leq n\leq 3000\right)\).
  • Dòng tiếp theo chứa \(n\) số nguyên dương \(l_1\), \(l_2\),..., \(l_n\). Dữ liệu đảm bảo dãy \(l\) là một dãy không giảm và các phần tử đều có giá trị không vượt quá \(3000\).
  • Dòng tiếp theo chứa \(n\) số nguyên dương \(r_1\), \(r_2\),..., \(r_n\). Dữ liệu đảm bảo dãy \(r\) là một dãy không giảm và các phần tử đều có giá trị không vượt quá \(3000\).
  • Dữ liệu đảm bảo \(l_i\le r_i\) với mọi \(1\le i\le n\).
Output
  • In ra một số nguyên thể hiện số lượng dãy không giảm thỏa mãn sau khi \(\text{mod}\) \(998244353\).
Ví dụ
Sample input 01
2
1 1
2 3
Sample output 01
5
Giải thích

Có \(5\) dãy không giảm thỏa mãn: \([1,1]\), \([1,2]\), \([1,3]\), \([2,2]\), và \([2,3]\).

Sample input 02
3
100 100 100
100 100 100
Sample output 02
1
Sample input 03
4
1 2 3 4 5
5 6 7 8 9
Sample output 03
126