Dotcpp  >  编程题库  >  蓝桥杯2020年第十一届国赛真题-质数行者
题目 2596:

蓝桥杯2020年第十一届国赛真题-质数行者

时间限制: 2s 内存限制: 192MB 提交: 286 解决: 21

题目描述

小蓝在玩一个叫质数行者的游戏。
游戏在一个 n×m×w 的立体方格图上进行,从北到南依次标号为第 1 行到
第 n 行,从西到东依次标号为第 1 列到第 m 列,从下到上依次标号为第 1 层到第 w 层。
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w层。每一步,他可以向东走质数格、向南走质数格或者向上走质数格。每走到一个位置,小蓝的角色要稍作停留。
在游戏中有两个陷阱,分别为第 r 1 行第 c 1 列第 h 1 层和第 r 2 行第 c 2 列第h2 层。这两个陷阱的位置可以跨过,但不能停留。也就是说,小蓝不能控制角色某一步正好走到陷阱上,但是某一步中间跨过了陷阱是允许的。
小蓝最近比较清闲,因此他想用不同的走法来完成这个游戏。所谓两个走法不同,是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下,他总共有多少种不同的走法。
提示:请注意内存限制,如果你的程序运行时超过内存限制将不得分。

输入格式

输入第一行包含两个整数 n, m, w,表示方格图的大小。
第二行包含 6 个整数,r 1 , c 1 , h 1 , r 2 , c 2 , h 2 ,表示陷阱的位置。

输出格式

输出一行,包含一个整数,表示走法的数量。答案可能非常大,请输出答
案除以 1000000007 的余数。

样例输入

5 6 1
3 4 1 1 2 1

样例输出

11

提示

【样例说明】
用 (r,c,h) 表示第 r 行第 c 列第 h 层,可能的走法有以下几种:

(1,1,1) − (1,3,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,3,1) − (3,3,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,3,1) − (3,3,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,3,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,3,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,4,1) − (5,6,1)。
(1,1,1) − (1,4,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,6,1)。
【评测用例规模与约定】
对于 30% 的评测用例 1 ≤ n,m,w ≤ 50。
对于 60% 的评测用例 1 ≤ n,m,w ≤ 300。
对于所有评测用例,1 ≤ n,m,w ≤ 1000,1 ≤ r 1 ,r 2 ≤ n, 1 ≤ c 1 ,c 2 ≤ m,
1 ≤ h 1 ,h 2 ≤ w,陷阱不在起点或终点,两个陷阱不同。

标签