/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の数列 A=(A_0,A_1,\ldots,A_{N-1}) が与えられます。
最初の時点では空の皿があり、高橋君は次の操作を 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 回目の操作において、X=0 であるので、アメは A_{(0\mod 5)}=A_0=2 個追加されます。
- 2 回目の操作において、X=2 であるので、アメは A_{(2\mod 5)}=A_2=6 個追加されます。
- 3 回目の操作において、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 bit 整数型に収まらない場合があります。
Score : 500 points
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.