Score : $500$ points

问题描述

你得到一个长度为 $N$ 的序列 $A=(A_0,A_1,\ldots,A_{N-1})$。

有一个初始时为空的盘子。Takahashi 将会重复进行以下操作 $K$ 次：

• 设 $X$ 为盘子上糖果的数量。他会再往盘子上添加 $A_{(X \bmod N)}$ 个糖果。这里，$X\bmod N$ 表示 $X$ 除以 $N$ 后的余数。

请计算在 $K$ 次操作后盘子上有多少个糖果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a sequence $A=(A_0,A_1,\ldots,A_{N-1})$ of length $N$.
There is an initially empty dish. Takahashi is going to repeat the following operation $K$ times.

• Let $X$ be the number of candies on the dish. He puts $A_{(X\bmod N)}$ more candies on the dish. Here, $X\bmod N$ denotes the remainder when $X$ is divided by $N$.

Find how many candies are on the dish after the $K$ operations.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $1 \leq K \leq 10^{12}$
• $1 \leq A_i\leq 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

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

Output

Print the answer.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the $1$-st operation, we have $X=0$, so $A_{(0\mod 5)}=A_0=2$ more candies will be put on the dish.
• In the $2$-nd operation, we have $X=2$, so $A_{(2\mod 5)}=A_2=6$ more candies will be put on the dish.
• In the $3$-rd operation, we have $X=8$, so $A_{(8\mod 5)}=A_3=3$ more candies will be put on the dish.

Thus, after the $3$ operations, there will be $11$ candies on the dish. Note that you must not print the remainder divided by $N$.

Sample Input 2

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

Sample Output 2

826617499998784056

The answer may not fit into a $32$-bit integer type.

update @ 2024/3/10 10:23:42