A7517. [AGC018E] Sightseeing Plan
编程题
NOI/NOI+/CTSC
知识点
题目描述
joisinoお姉ちゃん正在计划在高桥町观光。高桥町是一个以正方形区域组成、东西南北方向铺设的区域，从西边数第 $x$ 个、从北边数第 $y$ 个的区域称为区域 $(x, y)$。
joisinoお姉ちゃん认为，满足以下条件的观光计划是“好”的观光计划：
- 开始观光的区域为 $(p, q)$，其中 $X_1 \leq p \leq X_2$、$Y_1 \leq q \leq Y_2$。
- 吃午饭的区域为 $(s, t)$，其中 $X_3 \leq s \leq X_4$、$Y_3 \leq t \leq Y_4$。
- 结束观光的区域为 $(u, v)$，其中 $X_5 \leq u \leq X_6$、$Y_5 \leq v \leq Y_6$。
- 从观光开始区域到观光结束区域，必须恰好经过吃午饭的区域，且每一步只能走到相邻（边共享的）区域，并且总路程为最短距离。
如果两个观光计划在开始区域、吃午饭的区域、结束区域，或者途中经过的区域不同，它们就被视为不同的观光计划。
joisinoお姉ちゃん想知道有多少种“好”的观光计划。答案可能很大，请输出对 $10^9+7$ 取模的结果。
joisinoお姉ちゃん认为，满足以下条件的观光计划是“好”的观光计划：
- 开始观光的区域为 $(p, q)$，其中 $X_1 \leq p \leq X_2$、$Y_1 \leq q \leq Y_2$。
- 吃午饭的区域为 $(s, t)$，其中 $X_3 \leq s \leq X_4$、$Y_3 \leq t \leq Y_4$。
- 结束观光的区域为 $(u, v)$，其中 $X_5 \leq u \leq X_6$、$Y_5 \leq v \leq Y_6$。
- 从观光开始区域到观光结束区域，必须恰好经过吃午饭的区域，且每一步只能走到相邻（边共享的）区域，并且总路程为最短距离。
如果两个观光计划在开始区域、吃午饭的区域、结束区域，或者途中经过的区域不同，它们就被视为不同的观光计划。
joisinoお姉ちゃん想知道有多少种“好”的观光计划。答案可能很大，请输出对 $10^9+7$ 取模的结果。
输入格式
输入以如下格式从标准输入读入。
> $X_1$ $X_2$ $X_3$ $X_4$ $X_5$ $X_6$ $Y_1$ $Y_2$ $Y_3$ $Y_4$ $Y_5$ $Y_6$
> $X_1$ $X_2$ $X_3$ $X_4$ $X_5$ $X_6$ $Y_1$ $Y_2$ $Y_3$ $Y_4$ $Y_5$ $Y_6$
输出格式
输出“好”的观光计划总数，对 $10^9+7$ 取模。
输入输出样例
输入 #1
1 1 2 2 3 4 1 1 2 2 3 3
输出 #1
10
输入 #2
1 2 3 4 5 6 1 2 3 4 5 6
输出 #2
2346
输入 #3
77523 89555 420588 604360 845669 973451 2743 188053 544330 647651 709337 988194
输出 #3
137477680
说明/提示
## 限制条件
- $1 \leq X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6 \leq 10^6$
- $1 \leq Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6 \leq 10^6$
## 样例解释 1
观光开始区域只能为 $(1, 1)$，吃午饭的区域只能为 $(2, 2)$。
当观光结束区域为 $(3, 3)$ 时，移动方式有 $4$ 种；观光结束区域为 $(4, 3)$ 时，移动方式有 $6$ 种。
所以这个样例的答案为 $6+4=10$ 种。
由 ChatGPT 5 翻译
- $1 \leq X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6 \leq 10^6$
- $1 \leq Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6 \leq 10^6$
## 样例解释 1
观光开始区域只能为 $(1, 1)$，吃午饭的区域只能为 $(2, 2)$。
当观光结束区域为 $(3, 3)$ 时，移动方式有 $4$ 种；观光结束区域为 $(4, 3)$ 时，移动方式有 $6$ 种。
所以这个样例的答案为 $6+4=10$ 种。
由 ChatGPT 5 翻译