테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Subarray Divisibility ======

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

===== 코드 =====

==== collection.Counter를 사용해서 TLE가 나는 코드 ====
{{gh>https://github.com/teferi00/problem_solving/blob/main/problems/cses/q1662_tle.py}}

==== 그냥 list를 이용해서 카운팅 ====
{{gh>https://github.com/teferi00/problem_solving/blob/main/problems/cses/q1662.py}}

==== teflib.labs.intset.FrozenIntCounter를 사용 ====
{{gh>https://github.com/teferi00/problem_solving/blob/main/problems/cses/q1662_fic.py}}



{{tag>CSES}}