問題一覧 > 通常問題

No.1097 Remainder Operation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 205
作問者 : SSRSSSRS / テスター : 沙耶花沙耶花
8 ProblemId : 4385 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-25 22:19:36

問題文

整数$X$があります。$X$の最初の値は$0$です。また、長さ$N$の数列$A_0,A_1,\cdots,A_{N-1}$が与えられます。
これから、以下の操作を繰り返し行います。

操作: $X$を$N$で割った余りを計算し、$r$とする。$X$に$A_r$を加える。

$Q$回のクエリが来ます。それぞれのクエリでは、正の整数$K$が与えられるので、$K$回目の操作の後の$X$の値を求めてください。

入力

$N$
$A_0 \ A_1 \ \cdots \ A_{N-1}$
$Q$
$K_1$
$K_2$
$\vdots$
$K_Q$

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^6 (0 \leq i < N)$
  • $1 \leq Q \leq 10^5$
  • $1 \leq K_i \leq 10^{12} (1 \leq i \leq Q)$

出力

$Q$行出力してください。
$i (1 \leq i \leq Q)$行目には、$K_i$回目の操作の後の$X$の値を出力してください。

サンプル

サンプル1
入力
5
3 3 2 4 7
2
2
4
出力
7
16

$1$回目の操作では、$r=0$なので、$X=0+A_0=0+3=3$となります。
$2$回目の操作では、$r=3$なので、$X=3+A_3=3+4=7$となります。
$3$回目の操作では、$r=2$なので、$X=7+A_2=7+2=9$となります。
$4$回目の操作では、$r=4$なので、$X=9+A_4=9+7=16$となります。
よって、$2$回目と$4$回目の操作の後の$X$の値はそれぞれ$7, 16$なので、$7$と$16$を出力します。

サンプル2
入力
2
314159 141421
1
271828
出力
61919700120 

オーバーフローに注意してください。

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