102414: [AtCoder]ABC241 E - Putting Candies
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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.
Input
题意翻译
## 题目描述 [problemUrl]: https://atcoder.jp/contests/abc241/tasks/abc241_e 给你一个长度为 $ N $ 的数列$A $， $ A=(A_0,A_1,\ldots,A_{N-1}) $。 最初是空盘，高桥君会执行$K $次以下操作。 - 设盘子里有$ X $ 颗糖。每次在盘中放入$ A_{(X\bmod\ N)} $ 颗糖。 $ X\bmod\ N $ 表示 $ X $ 除以 $ N $ 的余数。 求$K$次后盘子里糖的颗数。 ## 输入格式 输入以以下形式从标准输入给出: > $ N $ $ K $ $ A_0 $ $ A_1 $ $ \ldots $ $ A_{N-1} $ ## 输出格式 输出答案 ## 提示 ### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ K\ \leq\ 10^{12} $ - $ 1\ \leq\ A_i\leq\ 10^6 $ - 输入都是整数Output
得分：500分
问题描述
给你一个长度为$N$的序列$A=(A_0,A_1,\ldots,A_{N-1})$。
- 有一个初始为空的盘子。Takahashi将要重复执行$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$位整数类型表示。