#9477. 黑洞(hole)

黑洞(hole)

黑洞(hole)

题目背景

注意:本场比赛提交时不开启文件输入输出。


上图给出了二维下与红点在同一条对角线上的所有方格。

考虑三维下的情况,下图给出了与红色方块在同一条对角线上的所有方块。

本题我们将会把对角线这个概念推广到 nn 维上。

题目描述

已知一片 nn 维空间,第 ii 维的大小为 mim_i。我们使用一个 nn 维坐标 (x1,x2,,xn)(x_1, x_2, \dots, x_n) 表示这片 nn 维空间里的一个位置,其中 xix_i[1,mi][1, m_i] 间的整数。

在位置 (a1,a2,,an)(a_1, a_2, \dots, a_n) 处有一颗黑洞。这片 nn 维空间中所有与它在同一条对角线上的位置都将被吞噬:

  • 称位置 (a1,a2,,an)(a_1, a_2, \dots, a_n)(b1,b2,,bn)(b_1, b_2, \dots, b_n) 在同一条对角线上,当且仅当存在一个整数 k0k \geq 0,使得对每个 1in1 \leq i \leq n,都有 aibi=k\lvert a_i - b_i \rvert = k

你需要求出共有多少个位置会被黑洞吞噬(即与黑洞在同一条对角线上,包括黑洞所处位置本身)。答案对 109+710^9 + 7 取模。

输入格式

第一行,一个正整数 nn,表示维度数。

第二行,nn 个正整数 m1,,mnm_1, \dots, m_n,表示每一维的大小。

第三行,nn 个正整数 a1,,ana_1, \dots, a_n,表示黑洞的位置。

输出格式

仅一行一个整数,表示该 nn 维空间中被黑洞吞噬的位置个数。答案对 109+710^9 + 7 取模。

样例 #1

样例输入 #1

2
6 6 
2 3

样例输出 #1

8

样例 #2

样例输入 #2

2
999999999 999999999
500000000 500000000

样例输出 #2

999999990

样例 #3

样例输入 #3

3
5 7 8
4 5 2

样例输出 #3

12

提示

【样例解释 #1】

如题目背景中的图所示,其中红色圆形为黑洞所在位置,黑色方格为被黑洞吞噬的位置,共 88 个。

【样例解释 #2】

19999999971999999997 个位置被黑洞吞噬,19999999971999999997109+710^9+7 取模的结果为 999999990999999990

【样例解释 #3】

如题目背景中的图所示,(1,2,5)(1,2,5)(2,3,4)(2,3,4)(2,7,4)(2,7,4)(3,4,1)(3,4,1)(3,4,3)(3,4,3)(3,6,1)(3,6,1)(3,6,3)(3,6,3)(4,5,2)(4,5,2)(5,4,1)(5,4,1)(5,4,3)(5,4,3)(5,6,1)(5,6,1)(5,6,3)(5,6,3)1212 个位置被黑洞吞噬。

【样例 #4】

见附件中的 hole/hole4.inhole/hole4.ans

该组样例满足测试点 9109 \sim 10 的约束条件。

【样例 #5】

见附件中的 hole/hole5.inhole/hole5.ans

该组样例满足测试点 111311 \sim 13 的约束条件。

【样例 #6】

见附件中的 hole/hole6.inhole/hole6.ans

该组样例满足测试点 141914 \sim 19 的约束条件。

【样例 #7】

见附件中的 hole/hole7.inhole/hole7.ans

该组样例满足测试点 202520 \sim 25 的约束条件。

【数据范围】

本题共 2525 个测试点,每个 44 分。

测试点编号 nn mim_i\le
121\sim2 =2=2 10610^6
343\sim4 10910^9
565\sim6 =3=3 10610^6
787\sim8 10910^9
9109\sim10 20\le20 1515
111311\sim13 10910^9
141914\sim19 1000\le1000
202520\sim25 2×105\le2\times10^5

对于全部数据,保证:2n2×1052\le n\le 2\times10^51aimi1091\le a_i\le m_i\le 10^9

样例下载