boj 3673 나눌 수 있는 부분 수열

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

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

M으로 나누어 떨어지는 연속하는 부분 수열의 합의 갯수를 찾는 문제입니다.

이 문제의 키워드는 "연속" 이며, 누적 합을 이용합니다.

 

M = 4, N = 8
2 1 2 1 1 2 1 2

위의 입력을 예시로 우선 수열의 누적합을 구해 각각의 MOD M을 구합니다.

 

sum   = 2 3 5 6 7 9 10 12
MOD M = 2 3 1 2 3 1 2 0

그러면 위와 같이 누적 합과 누적 합의 MOD M 값을 카운팅합니다.

 

M = 4이므로

나머지가 0인 갯수는 1

나머지가 1인 갯수는 2

나머지가 2인 갯수는 3

나머지가 3인 갯수는 2

이렇게 됩니다.

 

여기서 나머지가 1인 부분 수열을 설명하면

sum(1 ~ 3), sum(1 ~ 6)의 나머지가 1로 같다는 말입니다.

그러면 sum(4 ~ 6)의 나머지는 0이라는 말이 됩니다.

따라서 나머지가 같은 부분 수열에서 2개를 뽑는 조합을 구하면 되는 겁니다.

 

나머지가 1인 부분 수열은 2개이므로 2개 중에 2개를 뽑는 경우의 수: 1

 

나머지가 2인 부분 수열은

sum(1 ~ 1), sum(1 ~ 4), sum(1 ~ 7)로 3개로

3개 중에 2개를 뽑는 경우의 수로 3이라는 답이 나옵니다.

 

같은 방식으로 나머지가 0 ~ M - 1일 때의 경우의 수를 모두 구해줍니다.

 

 

#include <iostream>
#include <cstring>
#define MAX_N 50001
#define MAX_M 1000000
using namespace std;
typedef long long ll;
 
ll dp[MAX_N], cnt[MAX_M];
int N, M;
 
void func() {
    ll ans = cnt[0];
    for (int i = 0; i < M; i++) {
        if (cnt[i] < 2) continue;
        ans += ((cnt[i] * (cnt[i] - 1)) / 2LL);
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
        dp[i] += dp[i - 1];
 
        cnt[dp[i] % M]++;
    }
}
 
void init() {
    memset(cnt, 0, sizeof(cnt));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
        init();
    }
 
    return 0;
}