Subarray Divisibility

풀이

누적합 (Prefix sums) 을 이용하는 기본 유형의 문제
누적합을 n으로 나눈 나머지들로 누적합 배열을 만든 다음, 같은 값을 갖는 인덱스 쌍의 개수를 세어주면 된다.
간단한 문제이긴 하지만 주의할 점이 있는데, 같은 값을 갖는 인덱스들을 셀때, collections.Counter 나 dict등의 해시 기반 자료구조를 사용하면 TLE가 난다. 의도적인지는 모르겠지만, Hash table hack 에 해당하는 데이터 셋이 들어있다.
- 그냥 일반적인 리스트를 이용해서 카운팅하면 아무 문제가 없다.