#P18938. [Mladen Manev 2019 A3] bmaze / 无限迷宫
[Mladen Manev 2019 A3] bmaze / 无限迷宫
无限迷宫(Infinite Maze)
题目描述
一个迷宫有 行、无限多列,行列下标从1开始。第 行、第 列的格子编号为 。
迷宫每 列构成一个区块。第一个区块中有一些禁用格子,后面每个区块重复相同的禁用位置。
一条路径可以从第一个区块中的任意允许格子开始。每一步只能走向下一列的同一行、上一行或下一行,不能离开迷宫,也不能进入禁用格子。求终点位于第 列的不同路径数,答案对 取模。起点可以位于第一个区块的任何一列;仅起点不同的路径也不同。
禁用格子通过一个长度为 的编号序列指定。令 ,之后
序列中出现的编号均为禁用格子;同一编号重复出现时仍只禁用该格子一次。
输入格式
第一行三个整数 。第二行五个整数 。
输出格式
输出所求路径数模 的结果。
数据范围
,,,。
样例
4 8 3
7 1 2 7 11
12
样例说明
第一个区块的禁用编号为1、10、6、9、4、5、7。允许的起点编号为2、3、8、11、12。第8列中只有编号32的格子允许进入,共有12条路径到达这里。
来源与数据说明
2019 年 Dr. Mladen Manev,A3,原题名 bmaze。赛事资料,原文题面见附件 statement.pdf。
本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。