Count Arithmetic Progression
题目描述
给定两个长度为 N 的整数序列 L=(L1,L2,…,LN) 和 R=(R1,R2,…,RN)。
请统计满足下列条件的整数序列 A=(A1,A2,…,AN) 的数量,答案对 998244353 取模:
- 对每个 1≤i≤N,都有 Li≤Ai≤Ri。
- 令 d=A2−A1,对每个 1≤i<N,都有 Ai+1−Ai=d。
公差 d 可以为负数、零或正数。两个序列只要有一个位置的值不同,就视为不同序列。
输入格式
N
L_1 L_2 ... L_N
R_1 R_2 ... R_N
输入仅包含一组数据,所有数均为整数。
输出格式
输出一个整数,表示满足条件的序列数量对 998244353 取模的结果。
数据范围
- 2≤N≤3×105。
- 1≤Li≤Ri≤1012。
样例输入 1
3
5 5 2
7 6 7
样例输出 1
6
样例说明 1
六个序列分别为 (5,5,5)、(5,6,7)、(6,5,4)、(6,6,6)、(7,5,3)、(7,6,5)。
样例输入 2
4
2 3 1 6
5 6 4 8
样例输出 2
0