[백준/C++] 23827 수열(Easy)

https://www.acmicpc.net/problem/23827

23827번: 수열 (Easy)

 

# 문제 설명

- 모든 원소가 양의 정수이고, 길이가 N인 수열 A1, A2, ... , AN이 주어진다. 1<=i<j<=N을 만족하는 모든 정수쌍 (i,j)에 대해 Ai*Aj의 합을 1 000 000 007로 나눈 나머지를 구한다.

- 첫째 줄에 수열 A의 길이 N이 주어진다. (2<=N<=500000)

- 둘째 줄에 수열 A1, A2, ... , AN이 공백으로 구분되어 주어진다. (1<=Ai<=500000, 1<=i<=N)

 

# 풀이 방법

- 곱의 분배 법칙을 이용하여 a1*a2+a2*a3+a1*a3 을 a1*0+a2*a1+a3*(a1+a2) 형태로 바꾼다.

- 누적합을 이용하여 시간초과를 방지한다.

 

# 정답 코드

#include <iostream>
using namespace std;

long long n;
long long arr[500010];
long long ps[500010];
long long ans = 0;


int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		ps[i] = ps[i - 1] + arr[i];
		ans += arr[i] * ps[i - 1];
		ans %= 1000000007;
	}
	cout << ans;
}