백준 3673번 나눌 수 있는 부분수열

문제 링크입니다: https://www.acmicpc.net/problem/3673

배열을 입력받으면서 부분합을 D로 모듈러 연산을 한 결과의 개수를 visited 배열에 저장합니다.

$$이후,\; _{visited[i]}C_2의\; 누적합을\; 구해주면\; 됩니다.$$

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        for (int t = 0; t < T; t++)

        {

                 int D, N;

                 cin >> D >> N;

 

                 vector<long long> visited(MAX, 0);

                 int sum = 0;

 

                 visited[sum]++;

                 for (int i = 1; i <= N; i++)

                 {

                         int num;

                         cin >> num;

 

                         sum = (sum + num) % D;

                         visited[sum]++;

                 }

 

                 long long result = 0;

                 //visited[i] C 2

                 for (int i = 0; i < D; i++)

                         result += visited[i] * (visited[i] - 1) / 2;

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~