题面描述
对于一个用六边形无限平铺的平面,Pak Dengklek 站在其中一个格子上,并称该格子为初始格子。如果六边形平铺中的两个格子有公共边,则称它们是相邻的格子。对于一步移动,Pak Dengklek 可以从一个格子向六个可能的方向(编号为 1…6,如下图所示)移动到与其相邻的格子上。
对于某个由 N 次行动构成的行动序列,Pak Dengklek 可以用其产生的路径(对应一个按序访问的格子序
列)构造一个领域。其中第 i 次行动由移动方向 D[i] 和在该方向上的移动步数 L[i] 组成,并且该路径应有如下性质:
- 路径是封闭的,这意味着在格子序列中,起点格子与终点格子(即初始格子)相同。
- 路径是简单的,这意味着在格子序列中,除了初始格子访问过恰好两次(起点和终点分别访问一次),其他格子只能被访问至多一次。
- 路径是暴露的,这意味着在格子序列中,每个格子与至少一个不在序列中出现过的非内部格子相邻。
- 如果一个格子不在格子序列中出现过,并且从它出发,在不经过格子序列中任何格子的情况下,(通过若干步移动)只能访问到有限个格子,我们就称该格子是内部格子。
下图是一个符合上述条件的路径例子。其中:
- 1 号格子(粉色)是初始格子。
- 被编号的格子(淡蓝色)组成格子序列,编号代表它被访问的顺序。
- 被标上叉号的格子(深蓝色)是内部格子。
构造出的领域只包含所有路径上的格子和内部格子。领域中格子 c 的距离定义为:在只经过领域中包含格子的情况下,从初始格子出发到达 C 所需要的最少移动步数。领域中一个格子的分数定义为 A+d⋅B,其中 A 和 B 是 Pak Dengklek 给定的常数,d 是该格子在领域中的距离。下图给出了用上示路径构成的领域中每个格子的距离。
请帮助 Pak Dengklek 计算,用给出的行动序列构成的领域中,所有格子的分数之和。由于总分数值可能很大,最终结果对 109+7 取模。
实现细节
你需要实现下列函数:
int draw_territory(int N, int A, int B, int[] D, int[] L)
- N:行动序列中行动的次数。
- A, B:分数计算中的常数。
- D:大小为 N 的数组,其中 D[i] 表示第 i 次行动的方向。
- L:大小为 N 的数组,其中 L[i] 表示第 i 次行动的移动步数。
- 函数应该返回用给出的行动序列所构成的领域中,所有格子的分数总和对 109+7 取模后的值。
- 该函数将被调用恰好一次。
例子
考虑下列调用:
draw_territory(17, 2, 3,
[1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1],
[1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1])
该行动序列和上述题面中给出的例子相同。下表列出了该领域中所有可能的距离值所对应的分数。
距离值 |
格子数 |
每个格子分数 |
总分数 |
0 |
1 |
2+0×3=2 |
1×2=2 |
1 |
4 |
2+1×3=5 |
4×5=20 |
2 |
5 |
2+2×3=8 |
5×8=40 |
3 |
6 |
2+3×3=11 |
6×11=66 |
4 |
4 |
2+4×3=14 |
4×14=56 |
5 |
3 |
2+5×3=17 |
3×17=51 |
6 |
4 |
2+6×3=20 |
4×20=80 |
7 |
2+7×3=23 |
4×23=92 |
8 |
5 |
2+8×3=26 |
5×26=130 |
9 |
3 |
2+9×3=29 |
3×29=87 |
10 |
4 |
2+10×3=32 |
4×32=128 |
11 |
5 |
2+11×3=35 |
5×35=75 |
12 |
2 |
2+12×3=38 |
2×38=76 |
总分数值为 2+20+40+66+56+51+80+92+130+87+128+175+76=1003。
因此,draw_territory
应该返回 1003。
样例
17 2 3
1 1
2 2
3 2
4 1
5 1
4 1
3 1
2 2
1 3
6 2
2 3
3 1
4 6
5 3
6 3
6 2
1 1
1003
示例测试程序按如下方式读入数据:
- 第一行三个整数 N, A, B;
- 第 2+i 行每行两个整数 D[i], L[i] (0≤i≤N−1)。
示例测试程序按如下方式输出你的答案:
- 第一行一个数,表示
draw_territory
的返回值。
数据范围与提示
# |
分值 |
特殊限制 |
1 |
3 |
N=3, B=0 |
2 |
6 |
N=3 |
3 |
11 |
L 中的元素之和不超过 2000 |
4 |
12 |
B=0,L 中的元素之和不超过 200000 |
5 |
15 |
B=0 |
6 |
19 |
L 中的元素之和不超过 200000 |
7 |
18 |
L[i]=L[i+1] (0≤i≤N−2) |
8 |
16 |
无特殊限制 |
对于 100% 的数据,有 3<N<200000,0<A, B<109,1<D[i]<6, L[i]≥1(0≤i≤N−1),L 中的元素之和不超过 109,且给出的行动序列所对应的路径一定是封闭、简单和暴露的。