atcoder#ABC150E. [ABC150E] Change a Little Bit

[ABC150E] Change a Little Bit

配点 : 500500

問題文

0,10, 1 からなる長さ NN の異なる 22 つの数列 S,TS, T に対し、関数 f(S,T)f(S, T) を以下のように定めます。

  • SS に対し以下の操作を繰り返して TT と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S,T)f(S, T) である。
    • SiS_i を (00 から 11、もしくは 11 から 00 に) 変更する。この操作のコストは、変更の直前に SjTj(1jN)S_j \neq T_j (1 \leq j \leq N) であったような整数 jj の個数を DD として、D×CiD \times C_i である。

0,10, 1 からなる長さ NN の異なる 22 つの数列の組 (S,T)(S, T)2N×(2N1)2^N \times (2^N - 1) 通り考えられます。これらすべてに対する f(S,T)f(S, T) の和を 109+710^9+7 で割った余りを計算してください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ci1091 \leq C_i \leq 10^9
  • 入力は全て整数である

入力

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

NN

C1C_1 C2C_2 \cdots CNC_N

出力

f(S,T)f(S, T) の和を 109+710^9+7 で割った余りを出力せよ。

1
1000000000
999999993

0,10, 1 からなる長さ 11 の異なる 22 つの数列の組 (S,T)(S, T) は以下の 22 通りが考えられます。

  • S=(0),T=(1):S = (0), T = (1): S1S_111 に変更することでコスト 10000000001000000000S=TS = T とできるため、f(S,T)=1000000000f(S, T) = 1000000000 です。
  • S=(1),T=(0):S = (1), T = (0): S1S_100 に変更することでコスト 10000000001000000000S=TS = T とできるため、f(S,T)=1000000000f(S, T) = 1000000000 です。

これらの和は 20000000002000000000 であり、これを 109+710^9+7 で割った余りは 999999993999999993 です。

2
5 8
124

0,10, 1 からなる長さ 22 の異なる 22 つの数列の組 (S,T)(S, T)1212 通り存在し、例えば以下のものが考えられます。

  • S=(0,1),T=(1,0)S = (0, 1), T = (1, 0)

この場合、11 回目の操作で S1S_111 に変更し、22 回目の操作で S2S_200 に変更するとき、操作のコストの和は 5×2+8=185 \times 2 + 8 = 18 です。これより小さいコストで S=TS = T とすることはできないので、f(S,T)=18f(S, T) = 18 です。

5
52 67 72 25 79
269312