Suma de cubos de todos los subconjuntos de array dada

Dada una array arr[] , la tarea es calcular la suma de cubos de todos los posibles subconjuntos no vacíos de la array dada. Dado que la respuesta puede ser grande, imprima el valor como mod 1000000007.

Ejemplos:

Entrada: arr[] = {1, 2}
Salida: 18
subconjunto({1}) = 1 ³ = 1
subconjunto({2}) = 2 ³ = 8
subconjunto({1, 2}) = 1 ³ + 2 ³ = 1 + 8 = 9
Suma de cubos de todos los Subconjuntos = 1 + 8 + 9 = 18

Entrada: arr[] = {1, 1, 1}
Salida: 12

Enfoque ingenuo: un enfoque simple es encontrar todo el subconjunto y luego elevar al cubo cada elemento en ese subconjunto y agregarlo al resultado. La complejidad temporal de este enfoque será O(2 ^N )

Enfoque eficiente:

• Se puede observar que cada elemento del arreglo original aparece 2 ^{(N – 1)} veces en todos los subconjuntos.
• Por lo tanto, la contribución de cualquier elemento arr _i en la respuesta final será

  arri * 2(N – 1)

• Entonces, la Suma de cubos de todos los Subconjuntos será

  [arr03 + arr13 + arr23 + … + arr(N-1)3] * 2(N – 1)
  

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
  
#include <bits/stdc++.h>
using namespace std;
  
const int mod = 1e9 + 7;
  
// Function to return (2^P % mod)
long long power(int p)
{
    long long res = 1;
    for (int i = 1; i <= p; ++i) {
        res *= 2;
        res %= mod;
    }
    return res % mod;
}
  
// Function to return
// the sum of cubes of subsets
long long subset_cube_sum(vector<int>& A)
{
  
    int n = (int)A.size();
  
    long long ans = 0;
  
    // cubing the elements
    // and adding it to ans
    for (int i : A) {
        ans += (1LL * i * i * i) % mod;
        ans %= mod;
    }
  
    return (1LL * ans * power(n - 1))
           % mod;
}
  
// Driver code
int main()
{
    vector<int> A = { 1, 2 };
  
    cout << subset_cube_sum(A);
  
    return 0;
}

# Python3 implementation of the approach 
mod = int(1e9) + 7; 
  
# Function to return (2^P % mod) 
def power(p) :
  
    res = 1; 
    for i in range(1, p + 1) :
        res *= 2; 
        res %= mod; 
      
    return res % mod; 
  
# Function to return 
# the sum of cubes of subsets 
def subset_cube_sum(A) : 
  
    n = len(A); 
  
    ans = 0; 
  
    # cubing the elements 
    # and adding it to ans 
    for i in A :
        ans += (i * i * i) % mod; 
        ans %= mod; 
  
    return (ans * power(n - 1)) % mod; 
  
# Driver code 
if __name__ == "__main__" : 
  
    A = [ 1, 2 ]; 
  
    print(subset_cube_sum(A)); 
      
# This code is contributed by Yash_R

18

Complejidad de tiempo: O(N)