P15293 [MCO 2023] Segment Union

给定 $N$ 个正整数 $x_{1}, x_{2}, \ldots, x_{N}$ 以及另外 $N$ 个正整数 $a_{1}, a_{2}, \ldots, a_{N}$。 设 $P = (p_{1}, p_{2}, \ldots, p_{N})$ 是 $\{1, 2, \ldots, N\}$ 的一个排列。初始时，整个数轴为白色。对于每个 $1 \le i \le N$，将区间 $[x_{i} - a_{p_{i}}, x_{i} + a_{p_{i}}]$ 涂黑。定义 $f(P)$ 为数轴上黑色线段的总长度。例如，若涂黑的区间为 $[1, 3], [2, 4], [6, 7]$，则黑色线段的总长度为 $4 - 1 + 7 - 6 = 4$。 求所有 $\{1, 2, \ldots, N\}$ 的排列 $P$ 的 $f(P)$ 之和，并对 $10^{9} + 7$ 取模。

输入的第一行包含一个整数 $N$ （$1 \le N \le 1500$）。 输入的第二行包含 $N$ 个以空格分隔的整数 $x_{1}, x_{2}, \ldots, x_{N}$ （$-10^9 \le x_{i} \le 10^{9}$）。 输入的第三行包含 $N$ 个以空格分隔的整数 $a_{1}, a_{2}, \ldots, a_{N}$ （$1 \le a_{i} \le 10^{9}$）。

输出一个整数，表示所有 $\{1, 2, \ldots, N\}$ 的排列 $P$ 的 $f(P)$ 之和，对 $10^{9} + 7$ 取模后的结果。

#### 注释 **样例 1**： 长度为 $3$ 的排列共有 $3! = 6$ 个。设 $p$ 为排列。 - $p = (1, 2, 3)$：区间为 $[1,3]$， $[4,8]$， $[11,19]$，总长度 = $14$。 - $p = (1, 3, 2)$：区间为 $[1,3]$， $[2,10]$， $[13,17]$，总长度 = $13$。 - $p = (2, 1, 3)$：区间为 $[0,4]$， $[5,7]$， $[11,19]$，总长度 = $14$。 - $p = (2, 3, 1)$：区间为 $[0,4]$， $[2,10]$， $[14,16]$，总长度 = $12$。 - $p = (3, 1, 2)$：区间为 $[-2,6]$， $[5,7]$， $[13,17]$，总长度 = $13$。 - $p = (3, 2, 1)$：区间为 $[-2,6]$， $[4,8]$， $[14,16]$，总长度 = $12$。 答案为 $14 + 13 + 14 + 12 + 13 + 12 = 78$。 **样例 2**： 只有一个排列，唯一的区间为 $[-6, 8]$。答案为 $8 - (-6) = 14$。 **样例 3**： 注意可能存在重复的值。不同的排列可能产生相同的 $a$ 序列，但依然需要将它们重复计数（如同它们是不同的一样）。 **样例 4**： 此样例符合子任务 1 的约束条件。 **样例 5**： 记得输出答案对 $10^9 + 7$ 取模后的结果。 #### 计分 **子任务 1** （$7$ 分）： 所有 $a_i$ 相等，即对于所有 $i$ （$1 \le i \le n$）有 $a_i = a_1$ **子任务 2** （$8$ 分）： $N \le 9$， $-2000 \le x_i,\,a_i \le 2000$ **子任务 3** （$31$ 分）： $N \le 300$， $-10^5 \le x_i,\,a_i \le 10^5$ **子任务 4** （$17$ 分）： $N \le 300$ **子任务 5** （$25$ 分）： $-10^5 \le x_i,\,a_i \le 10^5$ **子任务 6** （$12$ 分）： 无额外限制 翻译由 DeepSeek 完成