Малефисумма

Давайте рассмотрим каждую тройку индексов $$$(i, j, k)$$$ в сумме и зафиксируем $$$j$$$. Для фиксированного $$$j$$$ в сумму входят произведения по всем $$$i < j$$$ и всем $$$k > j$$$.

Иными словами, перепишем нашу сумму как: $$$$$$\sum\limits_{j = 1}^n \Big(a_j \cdot \sum\limits_{i < j, k > j} a_i \cdot a_k\Big)$$$$$$

Поскольку выбор $$$i$$$ и $$$k$$$ не зависят друг от друга, можно переписать это как $$$$$$\sum\limits_{j = 1}^n \Big(a_j \cdot \big(\sum\limits_{i = 1}^{j - 1} a_i\big) \cdot \big(\sum\limits_{k = j + 1}^n a_k\big)\Big)$$$$$$

Заметим, что теперь каждое такое слагаемое можно считать за $$$\mathcal{O}(1)$$$ с $$$\mathcal{O}(n)$$$ предподсчета. Посчитаем префиксные суммы $$$b_i = a_1 + \ldots + a_i$$$ в одном цикле как $$$b_i = b_{i-1} + a_i$$$. Тогда теперь нам осталось просуммировать слагаемые вида $$$$$$a_j \cdot b_{j-1} \cdot (b_n - b_j)$$$$$$ по всем $$$j$$$ от $$$1$$$ до $$$n$$$. Суммарное время работы — $$$\mathcal{O}(n)$$$.