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

import sys

def input():
    return sys.stdin.readline().rstrip()

T = int(input())

for _ in range(T):
    d,n = map(int,input().split())

    mod = [ 0 for _ in range(d)]
    arr = list(map(int,input().split()))
    prefix_sum = [0] + arr[:]
    mod[0] += 1
    for i in range(n):
        prefix_sum[i+1] += prefix_sum[i]
        prefix_sum[i+1] %= d
        mod[prefix_sum[i+1]] += 1
    result = 0

    for i in range(d):
        result += (mod[i] * (mod[i]-1))//2

    print(result)

이 문제는 누적합을 활용한 문제이다. 

 

먼저 누적합을 구하면서 해당 누적합을 d로 나눈 나머지를 mod에 개수로 세어준다.

 

그러면 우리는 좌측부터 누적했을 때의 d로 나눴을 때  나오는 나머지의 값들이 언제 나오는지 알 수 있다.

 

그러면 우리는 d로 나눠지는 모든 경우의 수는

 

같은 나머지를 가지는 구간에서 2개를 뽑아서 그 두 구간을 빼주면 나머지가 0이 됨을 알 수 있다.

 

그러므로, 우리는 0부터 d-1까지 nC2를 해주면 된다.

 

그리고 우리는 0부터 하기 위해서, 0일때에 기본값으로 다른 나머지와 달리 1을 넣어주었다.