BOJ 13900 순서쌍의 곱의 합

주어진 N개의 정수로 만들 수 있는 순서쌍의 각각의 곱들의 합을 구하는 문제이다.
주어진 N개의 정수들로 만들 수 있는 조합의 각각의 곱들의 합을 구하는 문제로 보면 되는데, 내가  이 문제에 대해 생각한 것은 아니고 풀기전에 미리 풀이와 주의할 점을 들었기 때문에 바로 풀이와 주의할 점을 정리하겠다.

일단 주의할 점은 N개의 정수 중에서 2개를 뽑는 조합으로 보면 편하지만, 예를 들어 2, 2, 4가 주어지면 (2, 2), (2, 4) 로 끝이 아니라 (2, 2), (2, 4), (2, 4) 이렇게 3개이다.
그리고 오히려 이 주의할 점때문에 구하기가 편해진다.

만약 그냥 모든 순서쌍에 대해 일일이 다 구하려면 n이 10만개이기 때문에 O(n제곱)으로 시간초과가 날 것이다. 하지만 정말 멋진 방법이 있다.

이 문제에서 구하라는 것을 잘 보자.
각 조합에 속한 수의 곱의 합인데
2, 3, 4를 예로 들어보면
(2, 3), (2, 4), (3, 4) 이 세가지 조합에서 2*3 + 2*4 + 3*4 가 답이 된다.
잘 보면 2*(3+4) + 3*4로 나타낼 수 있다!!

그렇다. 미리 prefix sum을 구해놓게 되면 부분합을 O(1)만에 구할 수 있게 되고, 부분합을 알면 어떤 수x로 시작하는 조합의 곱들의 합을 O(1)만에 구할 수 있게 된다. 결국 문제에서 구하라고 하는 것을 O(n)만에 구할 수 있을 것이다.

AC를 받고 다른 분들의 풀이를 보니 이해는 잘 안 되지만 O(1)만에 구하신 분들도 있다... 그리고 어떤 분은 위의 과정을 그냥 입력받으면서 바로 처리하신 분도 있다... 별거 아닌 것 같아도 나는 생각도 못했는데...엄청나신 것 같다 다들...

추가 : 슬랙에 질문 게시판에 올라온 질문이 떠서 우연히 봤다.
이런 풀이도 있다  : https://www.acmicpc.net/board/view/10848