← 返回题目列表

AtCoder · abc241_e

H. 放置糖果

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个序列 A=(A_0,A_1,\ldots,A_{N-1}) 长度 N.
有一个最初是空的盘子。 高桥将重复以下操作 K 次。

  • 让 X 是盘子上糖果的数量。 他把 A_{(X\bmod N)} 盘子里有更多糖果。 在这里, X\bmod N 表示当 X 除以 N.

找出盘子上有多少糖果 K 操作。

约束

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq K \leq 10^{12}
  • 1 \leq A_i\leq 10^6
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_0 A_1 \ldots A_{N-1}

输出

打印答案。


示例输入 1

5 3
2 1 6 3 1

示例输出 1

11

盘子上的糖果数量变化如下。

  • 在 1-st 操作,我们有 X=0,所以 A_{(0\mod 5)}=A_0=2 盘子里会放更多糖果。
  • 在 2-nd操作,我们有 X=2,所以 A_{(2\mod 5)}=A_2=6 盘子里会放更多糖果。
  • 在 3-rd操作,我们有 X=8,所以 A_{(8\mod 5)}=A_3=3 盘子里会放更多糖果。

因此,之后 3 操作时,会有 11 盘子里有糖果。 请注意,您必须 不 打印除以的余数 N.


示例输入 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

示例输出 2

826617499998784056

答案可能不适合 32- 位整数类型。