[백준/BOJ] 백준 3673번 : 나눌 수 있는 부분 수열

www.acmicpc.net/problem/3673

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

각각의 지점에서 누적합을 d로 나누었을 때 값이 같은 것의 구간이 연속하는 부분 수열의 합이 d로 나누어 떨어지는 부분 수열이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int tc;
int d, n;
int input;
long long sum;
vector<long long> sum_list;
int rest[1000000];

void Pre()
{
	sum = 0;
	sum_list.clear();

	for (int i = 0; i < 1000000; i++)
		rest[i] = 0;

	rest[0] = 1; //시작지점, 나머지가 0인것 하나 추가
}

//number개중에 2개를 고르는 조합의 개수를 구한다
long long Combi2(long long number)
{
	if (number == 0 || number == 1)
		return 0;

	return (number*(number - 1)) / (2 * 1);
}

long long Solve()
{
	long long ret = 0;

	for (int i = 0; i < sum_list.size(); i++)
	{
		rest[sum_list[i] % d]++; //d로 나누었을때 값의 개수를 구한다
	}

	for (int i = 0; i < d; i++)
	{
		ret += Combi2(rest[i]); //d로 나누었을때 값이 같은것을 2개 묶는 조합의 개수를 구한다
	}

	return ret;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> d >> n;

		for (int i = 0; i < n; i++)
		{
			cin >> input;
			sum += input;
			sum_list.push_back(sum); //누적합을 저장한다
		}

		cout << Solve() << "\n";
	}

	return 0;
}