AT_abc150_e [ABC150E] Change a Little Bit

[problemUrl]: https://atcoder.jp/contests/abc150/tasks/abc150_e $ 0,\ 1 $ からなる長さ $ N $ の異なる $ 2 $ つの数列 $ S,\ T $ に対し、関数 $ f(S,\ T) $ を以下のように定めます。 - $ S $ に対し以下の操作を繰り返して $ T $ と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が $ f(S,\ T) $ である。 - $ S_i $ を ($ 0 $ から $ 1 $、もしくは $ 1 $ から $ 0 $ に) 変更する。この操作のコストは、変更の直前に $ S_j\ \neq\ T_j\ (1\ \leq\ j\ \leq\ N) $ であったような整数 $ j $ の個数を $ D $ として、$ D\ \times\ C_i $ である。 $ 0,\ 1 $ からなる長さ $ N $ の異なる $ 2 $ つの数列の組 $ (S,\ T) $ は $ 2^N\ \times\ (2^N\ -\ 1) $ 通り考えられます。これらすべてに対する $ f(S,\ T) $ の和を $ 10^9+7 $ で割った余りを計算してください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 $ 0,\ 1 $ からなる長さ $ 1 $ の異なる $ 2 $ つの数列の組 $ (S,\ T) $ は以下の $ 2 $ 通りが考えられます。 - $ S\ =\ (0),\ T\ =\ (1): $ $ S_1 $ を $ 1 $ に変更することでコスト $ 1000000000 $ で $ S\ =\ T $ とできるため、$ f(S,\ T)\ =\ 1000000000 $ です。 - $ S\ =\ (1),\ T\ =\ (0): $ $ S_1 $ を $ 0 $ に変更することでコスト $ 1000000000 $ で $ S\ =\ T $ とできるため、$ f(S,\ T)\ =\ 1000000000 $ です。 これらの和は $ 2000000000 $ であり、これを $ 10^9+7 $ で割った余りは $ 999999993 $ です。 ### Sample Explanation 2 $ 0,\ 1 $ からなる長さ $ 2 $ の異なる $ 2 $ つの数列の組 $ (S,\ T) $ は $ 12 $ 通り存在し、例えば以下のものが考えられます。 - $ S\ =\ (0,\ 1),\ T\ =\ (1,\ 0) $ この場合、$ 1 $ 回目の操作で $ S_1 $ を $ 1 $ に変更し、$ 2 $ 回目の操作で $ S_2 $ を $ 0 $ に変更するとき、操作のコストの和は $ 5\ \times\ 2\ +\ 8\ =\ 18 $ です。これより小さいコストで $ S\ =\ T $ とすることはできないので、$ f(S,\ T)\ =\ 18 $ です。