← 返回比赛

竞赛正在进行中 MMOI Round 3

← 上一题下一题 →

A7464 | $轮回$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

> 终于结束的起点 > 终于写下句点 > 终于我们告别 > 终于我们又回到原点 > > ——五月天《终于结束的起点》 > 一个个 OIer 的竞赛生涯总是从一场 NOIp 开始，大多也在一场 NOIp 中结束，好似一次次轮回在不断上演。 如果这次 NOIp 是你的起点，那么祝你的 OI 生涯如同夏花般绚烂。 如果这次 NOIp 是你的终点，那么祝你的 OI 回忆宛若繁星般璀璨。 也许这是你最后一次在洛谷上打比赛，也许不是。 不过，无论如何，祝你在一周后的比赛里，好运。 > 当然，这道题也和轮回有关系。 > ——洛谷 P4994 终于结束的起点 题目背景 Steve 修建了一条长度为 $d$ 格的环形矿车轨道，位置按顺时针顺序编号为第 $0,1,2,\dots,d-1$ 格。环形铁轨上运行着一辆矿车，它遵循一个长度为 $n$ 的指令序列 $a_0,a_1,\dots,a_{n-1}$ 进行移动。 具体地，给定正整数 $m$，矿车最初在第 $0$ 格，从第 $0$ 天开始，在第 $i$ 天时，矿车会按照以下方式移动： 1. 若 $i\bmod m=0$，则将指令序列 $a$ 循环右移一次，即将序列 $a$ 从 $[a_0,a_1,\dots,a_{n-2},a_{n-1}]$ 变为 $[a_{n-1},a_0,a_1,\dots,a_{n-2}]$。 2. 矿车沿顺时针方向行驶 $a_{i\bmod n}$ 格。 请你帮 Steve 求出，在第 $t-1$ 天结束时，第 $t$ 天开始前，矿车位于哪个位置？

输入格式

每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据： 第一行包含四个正整数 $d,n,m,t$，分别表示路线的长度、指令序列的长度、循环右移的周期、操作的天数。 第二行包含 $n$ 个正整数 $a_0,a_1,\dots,a_{n-1}$，表示指令序列 $a$ 的值。

输出格式

对于每组测试数据，输出一行一个整数，表示矿车最终的位置。

输入输出样例

输入 #1

0 3
6 5 2 6
2 4 3 3 1
5 4 1 9
2 4 1 3
100 8 11 1000000000000000000
12 7 4 21 1 6 18 8

输出 #1

4
2
40

【样例解释】 对于第一组测试数据： * 第 $0$ 天，指令序列先变为 $[1,2,4,3,3]$，矿车顺时针移动 $a_0=1$ 格，到达第 $1$ 格； * 第 $1$ 天，矿车顺时针移动 $a_1=2$ 格，到达第 $3$ 格； * 第 $2$ 天，指令序列先变为 $[3,1,2,4,3]$，矿车顺时针移动 $a_2=2$ 格，到达第 $5$ 格； * 第 $3$ 天，矿车顺时针移动 $a_3=4$ 格，到达第 $3$ 格； * 第 $4$ 天，指令序列先变为 $[3,3,1,2,4]$，矿车顺时针移动 $a_4=4$ 格，到达第 $1$ 格； * 第 $5$ 天，矿车顺时针移动 $a_0=3$ 格，到达第 $4$ 格。 所以第 $5$ 天结束时矿车所在的位置是第 $4$ 格。 【数据范围】 测试点编号特殊性质$1-2$$T\le 10$，$t\le 10^5$$3-5$$T\le 10$，$n,m\le 500$$6$$n=m$$7-8$$m=2$$9-10$无 对于 $100\%$ 的测试数据，保证：$1\le T\le 10^4$，$1 \le n \le 2\times10^5$，$1\le m,t\le 10^{18}$，$1\le d,a_i\le 10^9$，单个测试点中所有测试数据的 $n$ 之和不超过 $2\times10^5$。

C++ 编辑器

输入

输出