[백준-10986] 나머지 합

누적합과 조합 계산식이 필요한 문제다.

일단 입력값을 보면 100만임을 봐서 최소 O(NlogN) 의 복잡도 내로 끝내야 함을 알 수 있다. 허나 이 문제의 경우 각 누적합을 통해 O(N) 복잡도로 끝낼 수 있다. 로직은 다음과 같다.

• 입력되는 배열을 순서대로 sum 배열에 넣되 m으로 나눈 나머지 값을 쭉 넣어준다.
• sum 배열을 순회하면서 원소를 pai 배열에 체킹해준다.
• pai 배열에 체킹된 순서로 순회하면서 조합식을 더하면 답이 된다.

이렇게 pai 배열을 둔 이유는 sum[i] - sum[j] = 0 이 되는 경우의 수를 찾아야 하는데 결국 sum[i] == sum[j] 인 경우를 찾는 것과 다름이 없다. 따라서 같은 값을 가지는 sum 배열의 원소들을 쭉 체킹해준 다음 nC2의 조합식에 따라 단순 계산해주게 되면 답이 나오게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long LL;

LL input;
LL sum[1000001];
LL pai[1001];
// 입력값이 100만 -> nlogn 으로 끝내야 한다.
int main() {
	int n;
	LL m;
	scanf("%d %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &input);
		sum[i] = sum[i - 1] + (input % m);
		sum[i] %= m;
	}
	
	for (int i = 1; i <= n; i++) 
		pai[sum[i]] += 1;
	
	LL res = 0;
	for (LL i = 0; i < m; i++) {
		if (!pai[i]) continue;
		if (i == 0) {
			res += (pai[i] * (pai[i] - 1)) / 2;
			res += pai[i];
		}
		else {
			res += (pai[i] * (pai[i] - 1)) / 2;
		}
	}
	printf("%lld", res);
	return 0;
}

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

10986번: 나머지 합