← 返回比赛

已结束 ACOI #1

← 上一题下一题 →

A4998 | $圆环游戏$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

cjdst 做了一个圆环游戏。在这个游戏中，你要在一张有 $N$ 个格子的环形地图内移动，编号依次别为 $1\sim N$，每个格子上有一个正整数 $A_i$。 你最开始所在的编号为 $1$，得分为 $0$。你将进行若干次操作，每次操作如下： 1. 投掷一个多面体骰子，记你当前所在的编号数为 $K$，得到的点数为 $X$。 2. 前进 $X$ 格，即前进至编号为 $((K + X - 1) \mod N) + 1$ 的格子。 3. 记你当前所在的格子的编号数为 $L$。 4. 将得分增加 $A_L$。 但是，cjdst 偷偷给这个多面体骰子动了手脚，当你在编号为 $K$ 的格子内时，无论怎么投掷，得到的点数均为 $B_K$。 现求当你在进行第 $M$ 次操作后的得分为多少，答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $N, M$。 第二行 $N$ 个正整数 $A_i$。第三行 $N$ 个正整数 $B_i$。

输出格式

一个正整数，表示进行 $M$ 次操作后的得分。

输入输出样例

输入 #1

5 3
2 3 2 1 5
2 3 4 3 1

输出 #1

样例解释 你需要执行 $3$ 步。 第 $1$ 步：前进 $2$ 格至编号为 $3$ 的格子，并将得分加 $2$。 第 $2$ 步：前进 $4$ 格至编号为 $2$ 的格子，并将得分加 $3$。 第 $3$ 步：前进 $3$ 格至编号为 $5$ 的格子，并将得分加 $5$。 因此，总得分为 $10$。 以下是测试点信息： 测试点$N$$M$$A_i,B_i$性质$1$$\le 10$$\le 10$$\le 10$数据为样例#1$2$$\le 10^3$$\le 5\times 10^5$$\le 10^5$A$3,4,5$$\le 10^3$$\le 5\times 10^5$$\le 10^5$无$6$$\le 2\times 10^5$$\lt 2^{64}$$\le 10^6$A$7$$\le 2\times 10^5$$\lt 2^{64}$$\le 10^6$B$8,9,10$$\le 2\times 10^5$$\lt 2^{64}$$\le 10^6$无$11$$\le 10^6$$\le 10^{2\times 10^5}$$\le 10^9$A$12$$\le 10^6$$\le 10^{2\times 10^5}$$\le 10^9$B$13,14,15$$\le 10^6$$\le 10^{2\times 10^5}$$\le 10^9$无 性质 A：保证 $N \mid B_1$。 性质 B：保证所有 $B_i$ 都相等。

C++ 编辑器

输入

输出