[백준 3673] 나눌 수 있는 부분 수열

문제

www.acmicpc.net/problem/3673

3673번: 나눌 수 있는 부분 수열

 

문제 풀이

1. n의 범위로 보아 연속된 부분수열의 합을 구하기 위해 누적합을 사용한다고 생각했습니다.

 

2. 시작점이 고정된 연속 부분수열의 합이 아니므로 구해야하는건 시작점을 s, 끝점을 e라 할 때, 구간[s,e]의 누적합이 (psum[e] - psum[s-1])%d ==0을 만족하는 (s,e)쌍을 찾는 것과 같았고, 이는 (psum[e] % d) == (psum[s - 1] % d)와 동치입니다. 

 

3. 따라서 누적 합 psum[i]를 d로 나눈 나머지 배열(mod[])을 만들어서 누적합을 구할 때 마다 mod[psum[i] % d]의 값을 하나씩 올려줍니다. 

 

4. k = (psum[i] % d)라 할 때, 구간 [0~ d - 1]을 만족하는 k에 대해 mod를 순회하며 그 값이 2보다 크거나 같은 경우 만족하는 인덱스들이 그 순서를 유지하며 (s,e)에 들어가는 것이므로 정답에 $mod[k]C$₂만큼 더해줍니다. (k가 0인 경우 구간[0 : 해당 인덱스]누적합의 나머지가 0인 것이므로 그 값은 위와 별개로 더해줍니다.)

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int tc, d, n;
vector<int> v;
vector<ll> psum, mod;
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> tc;
	while (tc--) {
		cin >> d >> n;
		v.clear(), v.resize(n + 1);
		psum.clear(), psum.resize(n + 1);
		mod.clear(), mod.resize(d);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
			psum[i] = psum[i - 1] + v[i];
			mod[psum[i] % d]++;
		}
		ll ans = 0;
		for (int k = 0; k < d; k++) {
			if (!k && mod[k]) ans += mod[k];
			if (mod[k] >= 2) ans += (mod[k] * (mod[k] - 1)) / 2;
		}
		cout << ans << '\n';
	}
}