atcoder#AGC006C. [AGC006C] Rabbit Exercise

[AGC006C] Rabbit Exercise

配点 : 800800

問題文

NN 匹のうさぎがいます。 うさぎ達は 11 から NN まで番号が振られています。 最初、うさぎ ii は数直線上の座標 xix_i にいます。

うさぎ達は体操をすることにしました。 11 セット分の体操は、次のような合計 MM 回のジャンプからなります。 jj 回目のジャンプでは、うさぎ aja_j (2ajN12 \leq a_j \leq N-1) がジャンプします。 このとき、うさぎ aj1a_j-1 かうさぎ aj+1a_j+1 のどちらかが等確率で選ばれ(これをうさぎ xx とします)、うさぎ aja_j はうさぎ xx に関して対称な座標へジャンプします。

以上の合計 MM 回のジャンプを 11 セット分の体操として、うさぎ達は KK セット分の体操を続けて繰り返します。 各うさぎについて、最終的な座標の期待値を求めてください。

制約

  • 3N1053 \leq N \leq 10^5
  • xix_i は整数である。
  • xi109|x_i| \leq 10^9
  • 1M1051 \leq M \leq 10^5
  • 2ajN12 \leq a_j \leq N-1
  • 1K10181 \leq K \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

NN

x1x_1 x2x_2 ...... xNx_N

MM KK

a1a_1 a2a_2 ...... aMa_M

出力

NN 行出力せよ。 ii 行目には、うさぎ ii の最終的な座標の期待値を出力せよ。 絶対誤差または相対誤差が 10910^{-9} 以下ならば正解となる。

3
-1 0 2
1 1
2
-1.0
1.0
2.0

うさぎ 22 がジャンプします。 うさぎ 11 に関して対称な座標へジャンプすると、座標 2-2 へ移動します。 うさぎ 33 に関して対称な座標へジャンプすると、座標 44 へ移動します。 よって、うさぎ 22 の最終的な座標の期待値は 0.5×(2)+0.5×4=1.00.5 \times (-2)+0.5 \times 4=1.0 です。

3
1 -1 1
2 2
2 2
1.0
-1.0
1.0

xix_i は相異なるとは限りません。

5
0 1 3 6 10
3 10
2 3 4
0.0
3.0
7.0
8.0
10.0