A6478. 「CEOI2020」花式围栏
编程题
普及+/提高
知识点
题目描述
时间限制:$0.4s$
空间限制:$32MB$
众所周知,Balázs 拥有整个城镇中最漂亮的围栏。围栏由 $N$ 个部分组成,每个部分均为矩形,且相邻的两个部分间均紧密相连。第 $i$ 部分矩形的高度为 $h_i$,宽度为 $w_i$,我们需要找到满足如下条件的花式矩形:
- 矩形的每条边均是水平的或竖直的,且每条边的长度为整数。
- 矩形与地面的距离为整数。
- 矩形与围栏第一部分的左侧边的距离为整数。
- 矩形完整包含在围栏中。
现在你需要求出花式矩形的总数。因为这个数字可能很大,请输出其对 $10^9+7$ 取模后的结果。
空间限制:$32MB$
众所周知,Balázs 拥有整个城镇中最漂亮的围栏。围栏由 $N$ 个部分组成,每个部分均为矩形,且相邻的两个部分间均紧密相连。第 $i$ 部分矩形的高度为 $h_i$,宽度为 $w_i$,我们需要找到满足如下条件的花式矩形:
- 矩形的每条边均是水平的或竖直的,且每条边的长度为整数。
- 矩形与地面的距离为整数。
- 矩形与围栏第一部分的左侧边的距离为整数。
- 矩形完整包含在围栏中。
现在你需要求出花式矩形的总数。因为这个数字可能很大,请输出其对 $10^9+7$ 取模后的结果。
输入格式
输入第一行包含一个整数 $N$,代表围栏由 $N$ 部分组成。
第二行 $N$ 个整数,第 $i$ 个整数为第 $i$ 个矩形的高度 $h_i$。
第三行 $N$ 个整数,第 $i$ 个整数为第 $i$ 个矩形的宽度 $w_i$。
第二行 $N$ 个整数,第 $i$ 个整数为第 $i$ 个矩形的高度 $h_i$。
第三行 $N$ 个整数,第 $i$ 个整数为第 $i$ 个矩形的宽度 $w_i$。
输出格式
输出花式矩形数对 $10^9+7$ 取模后的结果。
输入输出样例
输入 #1
2 1 2 1 2
输出 #1
12
说明/提示
## 数据范围
$1 \leq N \leq 10^5$,$1 \leq h_i,w_i \leq 10^9$。
$1 \leq N \leq 10^5$,$1 \leq h_i,w_i \leq 10^9$。