Silhouette

silhouette.cpp/in/out

题目描述

有一个 $n \times n$ 的网格，在每个格子上堆叠了一些边长为 1 的立方体。

现在给出这个三维几何体的正视图和左视图，求有多少种与之符合的堆叠立方体的方案。两种方案被认为是不同的，当且仅当某个格子上立方体的数量不同。

输出答案对 $10^9 + 7$ 取模的结果。

从文件 silhouette.in 中读入数据。

第一行一个整数 $n$ 。

第二行 $n$ 个整数，第 $i$ 个表示正视图中从左到右第 $i$ 个位置的高度 $A_i$ 。

第三行 $n$ 个整数，第 $i$ 个表示左视图中从左到右第 $i$ 个位置的高度 $B_i$ 。

输出到文件 silhouette.out 中。

输出一行表示答案。

2
1 2
2 1

正视图和左视图：

  _       _
 _|_|     |_|_
|_|_|     |_|_|

如果用 $2 \times 2$ 的矩阵来表示每个格子上堆叠的立方体个数，则五种方案可以表示为：

1 2     0 2     1 2     0 2     1 2
1 1     1 0     1 0     1 1     0 1

3
3 1 3
2 3 2

3
1 1 1
3 3 3

见选手目录下的 silhouette/silhouette4.in 与 silhouette/silhouette4.ans。

见选手目录下的 silhouette/silhouette5.in 与 silhouette/silhouette5.ans。

对于所有数据，有 $1 \le n \le 10^5$ ， $1 \le A_i, B_i \le 10^9$ 。