#P18641. Count Arithmetic Progression

Count Arithmetic Progression

Count Arithmetic Progression

题目描述

给定两个长度为 NN 的整数序列 L=(L1,L2,…,LN)L=(L_1,L_2,\ldots,L_N) 和 R=(R1,R2,…,RN)R=(R_1,R_2,\ldots,R_N)。

请统计满足下列条件的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) 的数量,答案对 998244353998244353 取模:

  • 对每个 1≤i≤N1\le i\le N,都有 Li≤Ai≤RiL_i\le A_i\le R_i。
  • 令 d=A2−A1d=A_2-A_1,对每个 1≤i<N1\le i<N,都有 Ai+1−Ai=dA_{i+1}-A_i=d。

公差 dd 可以为负数、零或正数。两个序列只要有一个位置的值不同,就视为不同序列。

输入格式

N
L_1 L_2 ... L_N
R_1 R_2 ... R_N

输入仅包含一组数据,所有数均为整数。

输出格式

输出一个整数,表示满足条件的序列数量对 998244353998244353 取模的结果。

数据范围

  • 2≤N≤3×1052\le N\le 3\times10^5。
  • 1≤Li≤Ri≤10121\le L_i\le R_i\le10^{12}。

样例输入 1

3
5 5 2
7 6 7

样例输出 1

6

样例说明 1

六个序列分别为 (5,5,5)(5,5,5)、(5,6,7)(5,6,7)、(6,5,4)(6,5,4)、(6,6,6)(6,6,6)、(7,5,3)(7,5,3)、(7,6,5)(7,6,5)。

样例输入 2

4
2 3 1 6
5 6 4 8

样例输出 2

0