[BOJ 3673] 나눌 수 있는 부분 수열

양의 정수로 이루어진 수열에서 '연속하는 부분 수열의 합이 $d$로 나누어 떨어지는 것'의 개수를 구하는 문제이다.

 

단순하게 생각해 보면 모든 구간에 대해 확인을 해보면 된다.

하지만 이는 $O(n^2)$이 걸리며, 문제에서 $n$의 제한은 $50\ 000$까지이다. 

 

다른 방법을 생각해보자. 누적합을 이용해 볼 수 있을까?

$A_i$부터 $A_j$까지의 합을 7로 나눈 나머지가 3이라고 하자.

그리고 $A_k$까지의 합을 7로 나눈 나머지를 4라고 하자. $(i\lt j\lt k)$

그렇다면 $A_{j + 1}$부터 $A_k$까지의 합을 7로 나눈 나머지는 몇이 될까?

 

1이 될 것이다. $A\ mod\ M \equiv T_1$이고 $B\ mod\ M \equiv T_2$이면 $(A + B)\ mod\ M \equiv (T_1 + T_2)\ mod\ M$의 성질을 만족하기 때문이다. 

 

위의 상황을 바꾸어보면, $A_i$부터 $A_j$까지의 나머지와 $A_k$까지의 나머지가 같을 때, $A_{j + 1}$부터 $A_k$까지의 나머지가 0으로 $d$로 나누어 떨어지게 된다. 

 

즉, 나머지가 동일한 것끼리 선택을 하면 해당 구간은 나누어 떨어지게 된다. 그렇기에 나머지의 개수를 세어주고, $_nC_2$로 나머지가 같은 것 중 2개를 고른 경우의 수를 계속해서 답에 더해주면 된다.

 

이때, 아무것도 더하지 않은 상태를 추가해야 해서 나머지가 0인 개수를 1개로 초기화해 놓고 시작하는 것을 유의하자. 또한, 답과 계산과정에서 long long으로 넘어갈 수 있음을 유의하자. 

#define ll long long
#define MAXN 50001

ll c, d, n;
ll cnt[1000001];
ll A[MAXN], ans;

int main(void) {
    fastio;
    cin >> c;
    while (c--) {
        cin >> d >> n;
        memset(cnt, 0, sizeof(cnt)); cnt[0] = 1;
        for (int i = 1; i <= n; i++) {
            cin >> A[i];
            A[i] = (A[i] + A[i - 1]) % d;
            cnt[A[i]]++;
        }

        ans = 0;
        for (int i = 0; i < d; i++) {
            if (cnt[i] > 1)
                ans += cnt[i] * (cnt[i] - 1) / 2;
        }
        cout << ans << "\n";
    }
    return 0;
}