Найдите сумму подмножества с умножением

Легче вычислить сумму умноженных троек, когда разрешены повторения (например, a_1*a_1*a_1). Эта сумма составляет всего (sum^3).

Поскольку повторения запрещены, мы можем просто их вычесть: (sum^3 - 3*sumsquares*sum).

Но приведенная выше формула вычитает элементы на главной диагонали 3 раза, тогда как ее нужно вычесть только один раз. Нужно компенсировать это: (sum^3 - 3*sumsquares*sum + 2*sumcubes).

Приведенная выше формула не учитывает 3! перестановки каждой тройки. Значит надо разделить на 3!.

Наконец, у нас есть алгоритм с линейным временем:

1. Вычислить сумму заданных элементов мультимножества, сумму квадратов, сумму кубов.
2. result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6

Вот O(n^2) подход:

sum = SUM(list)
answer = 0
for each i from 0 to n:
   sum -= list[i]
   remains = sum
   for each j from i+1 to n:
      remains -= list[j]
      answer += list[i] * list[j] * (remains)

Это работает, потому что для каждых двух элементов x,y нужно суммировать x*y*z (для всех элементов z), но сумма всех возможных значений z равна SUM(list) - x - y.

Итак, вместо того, чтобы делать: x*y*z1 + x*y*z2 + ... + x*y*z(n-2), вы в основном делаете x*y*(z1 + ... + z(n-2))

РЕДАКТИРОВАТЬ: Отредактированный множественный подсчет из-за того, что он не умножается только в «хвосте», как упоминал @AbhishekBansal . Вам нужно умножить каждый элемент только на «хвост» списка, где хвост — это все элементы после последнего элемента среди x,y.

Полный рабочий код на C++ (продолжение идеи Амита)

#include <iostream>

using namespace std;

int main()
{
    int s[] = {3, 2, 1, 2};

    double sumOfFullList = 0;
    for ( int i = 0; i < 4; i++ )
        sumOfFullList += s[i];

    double sum = 0;

    for ( int i = 0; i < 4; i++ ) {
      double sumOfList = sumOfFullList - s[i];
      sumOfFullList -= s[i];
      for ( int j = i+1; j < 4; j++ ) {
          sumOfList -= s[j];
          sum += s[i]*s[j]*(sumOfList);
          //cout << s[i] << " " << s[j] << " " << sumOfList;
      }
    }

    cout << sum << endl;
    return 0;
}

Выход:

28