문제풀이

arr[i] = i까지의 연속합 일때
A(i)~A(j)까지의 합은 arr[j]-arr[i-1]이다.
이 문제는 arr[j]-arr[i-1]%m==0인 모든경우의 수를 구하는 것이다.
모듈러 연산은 나눗셈을 제외하고 분배법칙이 성립한다.
즉 (arr[j]%m-arr[i-1]%m)%m == 0 이고 arr[j]%m == arr[i-1]%m 이다.
arr[k]%m을 모든 k에 대해 구한다음 조합을 통해 빠르게 구하면 된다.
arr[j]%m == 0인 경우에는 독립적일때도 성립하기 때문에 경우의수를 한번더 계산해준다.

코드

solution

문제링크

boj/10986