Diferencia de subconjuntos


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Go, Java, Python, VB

Dado un arreglo A de n (3 \leq n \leq 10^5) elementos, calcule la suma de, para cada uno de los 2^n - 1 subconjuntos no vacíos del mismo, de la diferencia entre el máximo y el mínimo del subconjunto, para más detalle vea la explicación del ejemplo.

Los elementos del arreglo serán enteros entre 0 y 10^9.

Como la respuesta puede ser muy grande, imprímala módulo 10^9 + 7 (1000000007).

Subtareas:
  • Subtarea 1: n \leq 1000, los elementos de A son 0s o 1s. ( 15 puntos )

  • Subtarea 2: n \leq 16. ( 25 puntos )

  • Subtarea 3: n \leq 1000. ( 30 puntos )

  • Subtarea 4: n \leq 10^5. ( 30 puntos )

Entrada:
N
A_1 A_2 ... A_N
Salida:
answer
Ejemplo de entrada 1:
3
1 2 3
Ejemplo de salida 1:
6
Explicación del ejemplo 1:
Subconjunto       Diferencia entre máximo y mínimo
{1}                             0
{2}                             0
{3}                             0
{1, 2}                          1
{1, 3}                          2
{2, 3}                          1
{1, 2, 3}                       2
Ejemplo de entrada 2:
5
1 1 0 1 0
Ejemplo de salida 2:
21
Ejemplo de entrada 3:
6
1 3 2 7 8 4
Ejemplo de salida 3:
291

Comments

There are no comments at the moment.