問題一覧 > 通常問題

No.1307 Rotate and Accumulate

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 86
作問者 : 👑 stoqstoq / テスター : keymoonkeymoon
15 ProblemId : 4366 / 出題時の順位表
問題文最終更新日: 2020-12-01 23:41:54

問題文

長さ $N$ の 0-index の数列 $A=\{a_i\}, \ B=\{b_i\}$ があります。はじめ $B$ の要素は全て0です。

以下の操作を $Q$ 回行います。

  • $j$ 回目の操作では、$i = 0,1,\dots,N-1$ に対し、$b_i$ に $a_{i+r_j \ {\rm mod} \ N}$ を加える。
    ここで $X \ {\rm mod} \ M$ は $X$ を $M$ で割った余りを表す。

例えば $A = \{1,2,3\}, \ B = \{0,0,0\}, \ r_j = 1$ なら、操作を行うことで $B = \{2,3,1\}$ となります。

$Q$ 回の操作後の $B$ を求めてください。

入力

$N \ Q$
$a_0 \ a_1 \ \dots a_{N-1}$
$r_1 \ r_2 \ \dots r_Q$

  • 入力は全て整数
  • $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$

出力

操作後の $B=\{b_i\}$ を空白区切りで出力してください。

サンプル

サンプル1
入力
3 2
0 1 2
0 1
出力
1 3 2

1回目の操作では $b_0, b_1, b_2$ にそれぞれ 0, 1, 2 が加算され、 2回目の操作では $b_0, b_1, b_2$ にそれぞれ 1, 2, 0 が加算されます。

サンプル2
入力
5 5
2 7 1 8 2
0 1 2 3 4
出力
20 20 20 20 20

サンプル3
入力
7 9
1 1 2 3 5 8 13
1 4 1 4 2 1 3 5 6
出力
39 44 50 41 45 53 25

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。