백준 3673번 :: 나눌 수 있는 부분 수열 - C++

 

힌트

 

1. i번째부터 j번째까지 연속하는 부분수열의 합을 \(A_{i, j}\)라고 하면, \[A_{i, j} = A_{1, j} - A_{1, i}\] 이므로 '연속하는 부분 수열의 합'을 '두 개의 부분 수열 누적합의 차'로 표현할 수 있다.

 

2. 1번의 내용을 응용하면,

\[A_{i, j} \, mod \, d = (A_{1, j} - A_{1, i})  \, mod \, d = 0\]

이고, 이는 곧

\[A_{1, j} \, mod \, d = A_{1, i} \, mod \, d\]

이므로 '연속하는 부분 수열의 합이 d로 나누어 떨어지는 것'은 '두 부분 수열 누적합을 d로 나눴을 때의 나머지가 동일한 경우'와 같다.

 

3. 추가로 부분 수열 누적합의 나머지가 0인 경우 해당 부분 수열은 독자적으로 조건을 만족하므로 따로 계산해야 한다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> mod;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int c, d, n;
	cin >> c;

	for (int i = 0; i < c; ++i) {
		cin >> d >> n;

		// 누적합의 나머지 계산
		ll prev = 0;
		ll tmp;
		mod.clear();
		mod.resize(d);
		for (int j = 1; j <= n; ++j) {
			cin >> tmp;
			// 부분수열 누적합의 나머지를 계산
			prev = (prev + tmp) % d;
			// 해당 값을 나머지로 갖는 누적합의 갯수를 저장
			mod[prev]++;
		}
		
		ll result = 0;
		for (int j = 0; j < d; ++j) {
			// 나머지가 0인 경우 같은 값을 나머지로 갖는 누적합끼리 뺄 필요가 없다.
			// 해당 누적합은 단독으로 조건을 만족한다. 
			if (j == 0 && mod[j] > 0) result += mod[j];
			// 그 외에는 동일한 나머지 값을 갖는 누적합을 두개 골라 빼줘야 조건에 맞는 부분수열이 된다
			// Combination nC2 = n * (n - 1) / 2.
			if (mod[j] >= 2) result += mod[j] * (mod[j] - 1) / 2;
		}
		cout << result << "\n";
	}

	return 0;
}