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

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

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

누적합을 활용하여 해결할 수 있는 문제입니다. 테케가 200개이고 각 수열은 50000개가 가능하므로 10000000개의 수를 탐색해야해서 빠른 풀이를 찾다가 풀이법을 생각해냈습니다. 구간을 나누었을 때 d로 나누어진다는 것은 누적합들을 구했을 때 나머지가 같은 두 구간을 선택하여 빼주게 되면 d로 나누어지는 구간이 되게 됩니다. 그리고 구간을 선택하지 않고 현재까지 숫자를 모두 더했을 때에 d로 나누어떨어질 수 있는 케이스가 있으므로 조심해야합니다.

 

import sys

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

C = int(input())


for c in range(C):
    d, n = tuple(map(int, input().split()))
    nums = list(map(int, input().split()))
    mod = [0] * d
    cnt = 0
    sum = 0


    for num in nums:
        sum = (sum + num) % d

        # 나머지가 같은 구간까지의 개수만큼 더해주면 된다.
        cnt += mod[sum]
        mod[sum] += 1

        # 현재까지 숫자를 모두 더한 경우가 d로 나눠떨어지는 경우
        if sum == 0:
            cnt += 1

    print(cnt)