Skip to content

1311: Star War

题目

题目描述

Long ago in a galaxy far, far away, there was an empire that dominated all others...

第一秩序的领袖Kylo Ren亲自率领第一秩序庞大的西斯舰队,展开对宇宙黑暗的统治和杀戮。

在Leia的指令下,抵抗组织的军队向第一秩序的舰艇发动大规模袭击。Rey计划带领小分队潜入Emperor Palpatine所在的飞船,将沿途的路径告诉所有的反抗军,组织所有人对抗帕尔帕廷最后的军团。

大战所处的宇宙空间可以看做一个三位的有界区域,其中每个点$(x,y,z)$的坐标满足$0\leq x,y,z\leq n$,Rey带领的小分队所处在的位置为$(0,0,0)$,而敌人的飞船可能在坐标中的任何一个位置(坐标都是整数)。Rey想要知道如果敌军的坐标为$(x,y,z)$的时候,从起始位置有多少种路径可以到达敌军,以昭告天下。

规定Rey行军的方向只能向着最终目标前进,不能够走重复的回头路。(即如果当前位置为$(x_c,y_c,z_c)$,则下一步行军可以往$(x_c+1,y_c,z_c)$,$(x_c,y_c+1,z_c)$,$(x_c,y_c,z_c+1)$,$(x_c+1,y_c+1,z_c)$,$(x_c+1,y_c,z_c+1)$,$(x_c,y_c+1,z_c+1)$和$(x_c+1,y_c+1,z_c+1)$七个位置)

由于Rey不知道敌军的位置,所以询问可能会有非常多次。

本题对内存空间大小的要求比较特殊。对于宇宙大小的规模$n$,我们给出的空间为$O(n^2)$,希望大家利用所学知识,动态地利用内存空间。

输入格式

第一行两个整数$n$和$m$,分别表示空间的大小和询问的个数

第二行到第$m+1$行,每行三个整数$x$,$y$,$z$,表示询问的坐标

输出格式

$m$行,每行一个整数,表示方案数对$10^9 + 7$取模之后的结果

样例输入

text 5 6 2 3 1 4 0 2 0 3 4 4 4 4 3 4 3 3 3 3

样例输出

text 239 41 129 699121 50191 16081

数据范围

前$30\%$的数据$n\leq5$,其中$20\%$的数据$m\leq100$,另外$10\%$的数据$m\leq10^5$

另外$30\%$的数据$n\leq50$,$m\leq10$

另外$40\%$的数据$n\leq300$,$m\leq10^5$

请注意内存空间的限制

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!