(10986) 나머지 합

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

단계별로 풀어보기

22단계(누적 합) 4번째

 

 

누적합을 그대로 쓰는 게 아닌 조금 응용해야 하는 문제

누적합을 구한 뒤 2중 for문으로 모든 경우를 따지면 되는 거 아닌가? 라고 생각할 수 있지만 N의 범위가 백만이므로 O(N^2)가 걸리는 이 방법은 불가능하다.

누적합을 acc라 하면 조건을 만족하는 구간 (i,j)에서 구간합은 acc[j]-acc[i-1]이다. 이 값이 m으로 나뉘어야 하므로 acc[j]%m=acc[i-1]%m이다.

따라서 acc 전체에 m으로 모듈로 연산을 했을 때 값이 k인 원소가 x개라면, 이 중 두 개를 뽑으면 그 구간의 합은 m으로 나누어떨어진다. 이때 경우의 수는 x(x-1)/2이다. 이 계산을 0~m-1 전체에 하면 된다. acc[0]도 값이 0인 원소로 세줘야 하는 것을 주의하자(엄밀히 말하면 나머지가 0인 구간은 굳이 두 개를 고르지 않고 하나만 골라도 되는데, 이를 acc[0]을 고른 것처럼 계산해도 같은 결과가 나오는 것을 이용한 것이다).

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> acc(n+1), cnt(m);
  
  for(int i=1;i<=n;i++){
    cin >> acc[i];
    acc[i]= (acc[i]+acc[i-1])%m;
  }
  
  for(int i=0;i<=n;i++)  cnt[acc[i]]++;
  
  long ans= 0;
  
  for(int i=0;i<m;i++)  ans+= 1L*cnt[i]*(cnt[i]-1)/2;
  
  cout << ans;
  
  return 0;
}