A87 | [NOIP2020] 微信步数
来源NOIP提高组 / 2020
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
NOIP2020 T4
小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用 $k$ 维整数坐标 $(a_1, a_2, \ldots , a_k)$ 来表示其位置。场地有大小限制，第 $i$ 维的大小为 $w_i$，因此处于场地中的人其坐标应满足 $1 \le a_i \le w_i$（$1 \le i \le k$）。
小 C 打算在接下来的 $P = w_1 \times w_2 \times \cdots \times w_k$ 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 $n$ 步移动构成，每一步可以用 $c_i$ 与 $d_i$ 表示：若他当前位于 $(a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)$，则这一步他将会走到 $(a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)$，其中 $1 \le c_i \le k$，$d_i \in \{-1, 1\}$。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 $n$ 步后，若小 C 还在场内，他将回到第 $1$ 步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 $P$ 天之后，他一共刷出了多少步微信步数。请你帮他算一算。
小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用 $k$ 维整数坐标 $(a_1, a_2, \ldots , a_k)$ 来表示其位置。场地有大小限制，第 $i$ 维的大小为 $w_i$，因此处于场地中的人其坐标应满足 $1 \le a_i \le w_i$（$1 \le i \le k$）。
小 C 打算在接下来的 $P = w_1 \times w_2 \times \cdots \times w_k$ 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 $n$ 步移动构成，每一步可以用 $c_i$ 与 $d_i$ 表示：若他当前位于 $(a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)$，则这一步他将会走到 $(a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)$，其中 $1 \le c_i \le k$，$d_i \in \{-1, 1\}$。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 $n$ 步后，若小 C 还在场内，他将回到第 $1$ 步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 $P$ 天之后，他一共刷出了多少步微信步数。请你帮他算一算。
输入格式
第一行两个用单个空格分隔的整数 $n, k$。分别表示路线步数与场地维数。
接下来一行 $k$ 个用单个空格分隔的整数 $w_i$，表示场地大小。
接下来 $n$ 行每行两个用单个空格分隔的整数 $c_i, d_i$，依次表示每一步的方向，具体意义见题目描述。
接下来一行 $k$ 个用单个空格分隔的整数 $w_i$，表示场地大小。
接下来 $n$ 行每行两个用单个空格分隔的整数 $c_i, d_i$，依次表示每一步的方向，具体意义见题目描述。
输出格式
仅一行一个整数表示答案。答案可能很大，你只需要输出其对 ${10}^9 + 7$ 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 $-1$。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 $-1$。
输入输出样例
输入 #1
3 2 3 3 1 1 2 -1 1 1
输出 #1
21
输入 #2
5 4 6 8 6 5 3 1 2 1 1 1 2 1 2 -1
输出 #2
10265
**【样例 #1 解释】**
从 $(1, 1)$ 出发将走 $2$ 步，从 $(1, 2)$ 出发将走 $4$ 步，从 $(1, 3)$ 出发将走 $4$ 步。
从 $(2, 1)$ 出发将走 $2$ 步，从 $(2, 2)$ 出发将走 $3$ 步，从 $(2, 3)$ 出发将走 $3$ 步。
从 $(3, 1)$ 出发将走 $1$ 步，从 $(3, 2)$ 出发将走 $1$ 步，从 $(3, 3)$ 出发将走 $1$ 步。
共计 $21$ 步。
**【数据范围】**
| 测试点编号 | $n \le$ | $k \le$ | $w_i \le$ |
| :----------: | :---------------: | :-----: | :-------: |
| $1 \sim 3$ | $5$ | $5$ | $3$ |
| $4 \sim 6$ | $100$ | $3$ | $10$ |
| $7 \sim 8$ | ${10}^5$ | $1$ | ${10}^5$ |
| $9 \sim 12$ | ${10}^5$ | $2$ | ${10}^6$ |
| $13 \sim 16$ | $5 \times {10}^5$ | $10$ | ${10}^6$ |
| $17 \sim 20$ | $5 \times {10}^5$ | $3$ | ${10}^9$ |
对于所有测试点，保证 $1 \le n \le 5 \times {10}^5$，$1 \le k \le 10$，$1 \le w_i \le {10}^9$，$d_i \in \{-1, 1\}$。
**【附件下载】**
[walk.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/abkx8is1)
从 $(1, 1)$ 出发将走 $2$ 步，从 $(1, 2)$ 出发将走 $4$ 步，从 $(1, 3)$ 出发将走 $4$ 步。
从 $(2, 1)$ 出发将走 $2$ 步，从 $(2, 2)$ 出发将走 $3$ 步，从 $(2, 3)$ 出发将走 $3$ 步。
从 $(3, 1)$ 出发将走 $1$ 步，从 $(3, 2)$ 出发将走 $1$ 步，从 $(3, 3)$ 出发将走 $1$ 步。
共计 $21$ 步。
**【数据范围】**
| 测试点编号 | $n \le$ | $k \le$ | $w_i \le$ |
| :----------: | :---------------: | :-----: | :-------: |
| $1 \sim 3$ | $5$ | $5$ | $3$ |
| $4 \sim 6$ | $100$ | $3$ | $10$ |
| $7 \sim 8$ | ${10}^5$ | $1$ | ${10}^5$ |
| $9 \sim 12$ | ${10}^5$ | $2$ | ${10}^6$ |
| $13 \sim 16$ | $5 \times {10}^5$ | $10$ | ${10}^6$ |
| $17 \sim 20$ | $5 \times {10}^5$ | $3$ | ${10}^9$ |
对于所有测试点，保证 $1 \le n \le 5 \times {10}^5$，$1 \le k \le 10$，$1 \le w_i \le {10}^9$，$d_i \in \{-1, 1\}$。
**【附件下载】**
[walk.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/abkx8is1)
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？