AT_agc007_c [AGC007C] Pushing Balls

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_c $ N $ 個の球と $ N+1 $ 個の穴が一直線上に並んでいます。球には左から順に $ 1 $ から $ N $ の番号が、穴には左から順に $ 1 $ から $ N+1 $ の番号が振られています。$ i $ 番の球は $ i $ 番の穴と $ i+1 $ 番の穴の間に置かれており、隣り合う穴と球の間の距離を左から順に並べて得られる数列を $ d_i $ ($ 1\ \leq\ i\ \leq\ 2\ \times\ N $) とおきます。$ d_1 $ の値とパラメータ $ x $ が与えられており、$ d_i\ -\ d_{i-1}\ =\ x $ が任意の $ i $ ($ 2\ \leq\ i\ \leq\ 2\ \times\ N $) に対して成り立っています。 これら $ N $ 個の球を $ 1 $ 個ずつ転がし、穴に落としていくことを考えます。球が穴の上を通ると、その穴にすでに別の球が入っていなければその穴に落ちます。すでに別の球がその穴に入っていた場合は、球は落ちずにそのまま転がり続けます。（なお、この問題で考える球の転がし方において、球どうしが衝突することはありません。） 球を転がす際は、まだ転がされていない球の中から等確率で $ 1 $ つを選び、その球を左または右に等確率で転がします。これを $ N $ 回繰り返してすべての球を転がすとき、すべての球が移動する距離の総和の期待値を求めてください。 以下に $ N\ =\ 3 $, $ d_1\ =\ 1 $, $ x\ =\ 1 $ の場合の球の転がし方の例を挙げます。  1. $ 2 $ 番の球を左に転がす。球は $ 2 $ 番の穴に落ちる。球が移動する距離は $ 3 $ である。 2. $ 1 $ 番の球を右に転がす。球は $ 2 $ 番の穴の上を通り、$ 3 $ 番の穴に落ちる。球が移動する距離は $ 9 $ である。 3. $ 3 $ 番の球を右に転がす。球は $ 4 $ 番の穴に落ちる。球が移動する距離は $ 6 $ である。 この例では、球が移動する距離の総和は $ 18 $ となります。 なお、球をどのように転がしてもどの球も必ずいずれかの穴に落ち、最後に穴が一つだけ空のまま残ることになります。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 200,000 $ - $ 1\ \leq\ d_1\ \leq\ 100 $ - $ 0\ \leq\ x\ \leq\ 100 $ - 入力値はすべて整数である。 ### Sample Explanation 1 球が $ 1 $ 個、穴が $ 2 $ 個あります。球から左の穴までの距離は $ 3 $ 、球から右の穴までの距離は $ 6 $ です。球を左に転がすか右に転がすかの $ 2 $ 通りの転がし方があり、それぞれにおいて球が移動する距離は $ 3,\ 6 $ です。したがって、答えは $ (3+6)/2\ =\ 4.5 $ となります。