[백준/C++] 10986번: 나머지 합

문제

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

10986번: 나머지 합

---

문제 요약

N개의 이루어진 수열 A의 연속된 부분 수열의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

---

코드

???

---

코드 설명

0 ~ i 까지의 누적합

=> prefix[i]

 

부분 수열 (i + 1~ j) 의 합

=> prefix[j] - prefix[i]

 

부분 수열 (i + 1 ~ j) 의 합이 M으로 나뉜다.

=> (prefix[j] - prefix[i]) % M = 0

=> prefix[j] % M - prefix[i] % M = 0

 

 prefix_mod[i] : 누적합을 M으로 나눈 나머지가 i인 개수

 

누적합을 M으로 나눈 나머지가 같은 인덱스들 중 두 인덱스를 골라 차를 구하면 0이다.

 

따라서, Combination을 이용해 경우의 수를 계산하면 된다.

 

추가적으로 구간은 0부터 시작한다고 생각하고 있으므로, 0으로 나누어 떨어지는 것은 혼자서 존재할 수 있다. 따라서 결과값에 prefix_mod[0]을 더해야 한다.

+ 누적합이 0으로 나누어 떨어는 구간은 다른 누적합 구간을 빼지 않아도 0으로 나누어 떨어지기 때문이다.