It is easier to calculate sum of multiplied triplets when repetitions are allowed (like a_1*a_1*a_1). This sum is just (sum^3)
.
Since repetitions are not allowed, we could just subtract them: (sum^3 - 3*sumsquares*sum)
.
But the above formula subtracts elements on main diagonal 3 times while it should be subtracted only once. Need to compensate this: (sum^3 - 3*sumsquares*sum + 2*sumcubes)
.
The above formula does not take into account 3! permutations of each triplet. So it should be divided by 3!
.
Finally we have a linear-time algorithm:
- Compute sum of given multiset elements, sum of squares, sum of cubes.
result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6