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

문제 링크

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

23827번: 수열 (Easy)

 

문제

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

입력

첫째 줄에 수열 A의 길이 N이 주어진다.

둘째 줄에 수열 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.

출력

 1≤i<j≤N을 만족하는 모든 정수쌍 (i,j)에 대해 Ai×Aj의 합을 1000000007로 나눈 나머지를 출력하여라.

제한

•  2≤N≤500000
•  1≤Ai≤500000(1≤i≤N)

예제 입력 1

3
1 2 3

예제 출력 1

11

 1×2+2×3+1×3=11

알고리즘 분류

• 누적 합

풀이

이 문제랑 똑같은 문제다.

14929번: 귀찮아 (SIB)

누적 합을 구하고, i가 1부터 N까지인 i번째 수와 i+1번째 수부터 N번째 수까지의 합의 곱을 더해준다.

값이 크므로 자료형을 long long으로 하고, 1,000,000,007로 나눈 나머지를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 500001
#define LL long long
#define INF 1e9
#define MOD 1000000007

using namespace std;
int N;
LL MAP[MAX];
LL Sum[MAX];
LL Answer = 0;

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> MAP[i];
		Sum[i] = Sum[i - 1] + MAP[i];
	}
}


void Settings() {
	for (int i = 1; i <= N; i++) {
		Answer += ((Sum[N] - Sum[i]) * MAP[i]) % MOD;
	}
}

void Find_Answer() {
	cout << Answer % MOD << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}