2020年第十一届蓝桥杯决赛JAVA B J题“质数行者“

本文主要是介绍2020年第十一届蓝桥杯决赛JAVA B J题“质数行者“，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2020年第十一届蓝桥杯决赛JAVA B J题"质数行者"

【问题描述】
小蓝在玩一个叫质数行者的游戏。
游戏在一个 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 列第h 2 层。这两个陷阱的位置可以跨过,但不能停留。也就是说,小蓝不能控制角色某一步正好走到陷阱上,但是某一步中间跨过了陷阱是允许的。
小蓝最近比较清闲,因此他想用不同的走法来完成这个游戏。所谓两个走法不同,是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下,他总共有多少种不同的走法。
提示:请注意内存限制,如果你的程序运行时超过内存限制将不得分。

【输入格式】
输入第一行包含两个整数 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) − (1, 3, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
2. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
3. (1, 1, 1) − (1, 3, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
4. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (3, 6, 1) − (5, 6, 1)。
5. (1, 1, 1) − (3, 1, 1) − (3, 3, 1) − (5, 3, 1) − (5, 6, 1)。
6. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 3, 1) − (5, 6, 1)。
7. (1, 1, 1) − (3, 1, 1) − (5, 1, 1) − (5, 4, 1) − (5, 6, 1)。
8. (1, 1, 1) − (1, 4, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
9. (1, 1, 1) − (1, 6, 1) − (3, 6, 1) − (5, 6, 1)。
10. (1, 1, 1) − (3, 1, 1) − (3, 6, 1) − (5, 6, 1)。
11. (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,陷阱不在起点或终点,两个陷阱不同。

解析：这题比前三体简单多了，题目还友好提升可能会爆内存，那么傻乎乎的dfs肯定是不可取了。
（1）线性晒筛出所有能走的质数步
（2）dp[i][j][k] 能从任何非陷阱位置通过质数步走到。dp[i][j][k]+ = dp[i-x][j][k] and dp[i][j-x][k] and dp[i][j][k-x] ,x为满足条件的质数步
（3）输出dp[max i ][max j][max k]即可

（代码稍后补上）

这篇关于2020年第十一届蓝桥杯决赛JAVA B J题“质数行者“的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！