atcoder#AGC006C. [AGC006C] Rabbit Exercise

[AGC006C] Rabbit Exercise

题目描述

N N 匹のうさぎがいます。 うさぎ達は 1 1 から N N まで番号が振られています。 最初、うさぎ i i は数直線上の座標 xi x_i にいます。

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

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

输入格式

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

N N x1 x_1 x2 x_2 ... ... xN x_N M M K K a1 a_1 a2 a_2 ... ... aM a_M

输出格式

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

题目大意

nn 只兔子在一个数轴上,兔子为了方便起见从 11nn 标号,第 ii 只兔子的初始坐标为 xix _ i
兔子会以以下的方式在数轴上锻炼:一轮包含 mm 个跳跃,第 jj 次跳跃是兔子 aj(2ajN1)a _ j(2≤a _ j ≤N-1) 跳一下,这一下从兔子 aj1a _ j - 1 和兔子 aj+1a _ j + 1 中等概率的选一个。假设选了 xx,那么 aja _ j 号兔子会跳到它当前坐标关于 xx 的坐标的对称点。
注意,即使兔子的位置顺序变化了,但是编号仍保持不变,这里按兔子编号算。
兔子会进行 kk 轮跳跃,对每个兔子,请你求出它最后坐标的期望值。

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

提示

制約

  • 3 < =N < =105 3\ <\ =N\ <\ =10^5
  • xi x_i は整数である。
  • xi < =109 |x_i|\ <\ =10^9
  • 1 < =M < =105 1\ <\ =M\ <\ =10^5
  • 2 < =aj < =N1 2\ <\ =a_j\ <\ =N-1
  • 1 < =K < =1018 1\ <\ =K\ <\ =10^{18}

Sample Explanation 1

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

Sample Explanation 2

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