[AGC006C] Rabbit Exercise
题意翻译
有 $n$ 只兔子在一个数轴上,兔子为了方便起见从 $1$ 到 $n$ 标号,第 $i$ 只兔子的初始坐标为 $x _ i$。
兔子会以以下的方式在数轴上锻炼:一轮包含 $m$ 个跳跃,第 $j$ 次跳跃是兔子 $a _ j(2≤a _ j ≤N-1)$ 跳一下,这一下从兔子 $a _ j - 1$ 和兔子 $a _ j + 1$ 中等概率的选一个。假设选了 $x$,那么 $a _ j$ 号兔子会跳到它当前坐标关于 $x$ 的坐标的对称点。
注意,即使兔子的位置顺序变化了,但是编号仍保持不变,这里按兔子编号算。
兔子会进行 $k$ 轮跳跃,对每个兔子,请你求出它最后坐标的期望值。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc006/tasks/agc006_c
$ N $ 匹のうさぎがいます。 うさぎ達は $ 1 $ から $ N $ まで番号が振られています。 最初、うさぎ $ i $ は数直線上の座標 $ x_i $ にいます。
うさぎ達は体操をすることにしました。 $ 1 $ セット分の体操は、次のような合計 $ M $ 回のジャンプからなります。 $ j $ 回目のジャンプでは、うさぎ $ a_j $ ($ 2\ <\ =a_j\ <\ =N-1 $) がジャンプします。 このとき、うさぎ $ a_j-1 $ かうさぎ $ a_j+1 $ のどちらかが等確率で選ばれ(これをうさぎ $ x $ とします)、うさぎ $ a_j $ はうさぎ $ x $ に関して対称な座標へジャンプします。
以上の合計 $ M $ 回のジャンプを $ 1 $ セット分の体操として、うさぎ達は $ K $ セット分の体操を続けて繰り返します。 各うさぎについて、最終的な座標の期待値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ x_1 $ $ x_2 $ $ ... $ $ x_N $ $ M $ $ K $ $ a_1 $ $ a_2 $ $ ... $ $ a_M $
输出格式
$ N $ 行出力せよ。 $ i $ 行目には、うさぎ $ i $ の最終的な座標の期待値を出力せよ。 絶対誤差または相対誤差が $ 10^{-9} $ 以下ならば正解となる。
输入输出样例
输入样例 #1
3
-1 0 2
1 1
2
输出样例 #1
-1.0
1.0
2.0
输入样例 #2
3
1 -1 1
2 2
2 2
输出样例 #2
1.0
-1.0
1.0
输入样例 #3
5
0 1 3 6 10
3 10
2 3 4
输出样例 #3
0.0
3.0
7.0
8.0
10.0
说明
### 制約
- $ 3\ <\ =N\ <\ =10^5 $
- $ x_i $ は整数である。
- $ |x_i|\ <\ =10^9 $
- $ 1\ <\ =M\ <\ =10^5 $
- $ 2\ <\ =a_j\ <\ =N-1 $
- $ 1\ <\ =K\ <\ =10^{18} $
### Sample Explanation 1
うさぎ $ 2 $ がジャンプします。 うさぎ $ 1 $ に関して対称な座標へジャンプすると、座標 $ -2 $ へ移動します。 うさぎ $ 3 $ に関して対称な座標へジャンプすると、座標 $ 4 $ へ移動します。 よって、うさぎ $ 2 $ の最終的な座標の期待値は $ 0.5×(-2)+0.5×4=1.0 $ です。
### Sample Explanation 2
$ x_i $ は相異なるとは限りません。