[BOJ] 3673번: Divisible Subsequences

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

어디선가 본 문제인데 찾지를 못하겠네요. $S[i] = sum(A[0 to i])$라고 할 때 $sum[i to j] = S[j]-S[i-1]$이므로 $S[0], S[1], ... , S[N]$ 각각의 D로 나눈 나머지의 갯수를 셉니다. 예를 들어 D = 3이고 1 2 3 1 2라는 수열을 생각해보면 나머지가 0인 것은 S[0], S[3], S[5], 1인 것은 S[1], S[4]이므로 $\binom{3}{2}+\binom{2}{2}$ 가 답이 됩니다.

https://github.com/blisstoner/BOJ/blob/master/3673.cpp