설명

• 누적합으로 푸는데 일반적인 방식으로는 O($n^2$) 걸리니 어떻게 풀어야될까 계속 고민
  • 두시간 걸렸다..
• 나머지를 사용해서 풀이하면 M이 $10^3$이하이므로 시간복잡도상으로 충분하다고 판단했다.
  • 나머지 0인 경우는 자기 자신만 있어도 되니까 더해준다.
  • 그 다음부터 조합을 적용

코드

package Baekjoon;

import java.io.*;
import java.util.*;
public class Algo10986 {

    static int N,M;
    static int[] remainder;
    static long[] accSum;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        accSum = new long[N+1];
        remainder = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            accSum[i] = accSum[i-1] + Integer.parseInt(st.nextToken());
            remainder[(int)(accSum[i] % M)]++;
        }
        long result = (long)remainder[0]*(remainder[0]-1)/2 + remainder[0];

        for(int diff=1; diff<M; diff++) {
            result += (long) remainder[diff] *(remainder[diff]-1)/2;
        }

        System.out.println(result);
    }
}