No.1307 Rotate and Accumulate
stoq
keymoonProblem Statement
There are 0-indexed sequences $A= (a_i), \ B=(b_i)$ of length $N$. Initially, all elements of $B$ are $0$.
Perform the following operation $Q$ times.
- In the $j$-th operation, for each $i = 0,1,\dots,N-1$, add $a_{i+r_j \ {\rm mod} \ N}$ to $b_i$.
Here, $X \ {\rm mod} \ M$ denotes the remainder when $X$ is divided by $M$.
For example, if $A = (1,2,3), \ B = (0,0,0), \ r_j = 1$, performing the operation results in $B = (2,3,1)$.
Find $B$ after the $Q$ operations.
Input
$N \ Q$
$a_0 \ a_1 \ \dots a_{N-1}$
$r_1 \ r_2 \ \dots r_Q$
- All inputs are integers.
- $1 \leq N \leq 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq a_i \leq 10^3$
- $0 \leq r_i \leq N-1$
Output
Print $B$ after the operations, separated by spaces.
Sample
Sample 1
Input
3 2 0 1 2 0 1
Output
1 3 2
In the 1st operation, $0, 1, 2$ are added to $b_0, b_1, b_2$ respectively, and in the 2nd operation, $1, 2, 0$ are added to $b_0, b_1, b_2$ respectively.
Sample 2
Input
5 5 2 7 1 8 2 0 1 2 3 4
Output
20 20 20 20 20
Sample 3
Input
7 9 1 1 2 3 5 8 13 1 4 1 4 2 1 3 5 6
Output
39 44 50 41 45 53 25
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。