(백준/c++) 10986 - 나머지 합

 

10986번: 나머지 합 (acmicpc.net)

10986번: 나머지 합

※틀린 답: 시간초과 (N^2)

 

 

 

 

왜 틀렸는지.. 그럼 어떻게 풀어야하는지.. 질문검색을 뒤져보는 중에..

무슨 말이지??? ..

그래서 예제를 이용해서 천천히 정리해보았다.

---

1. 부분합을 M으로 나눈 나머지가 같은 것끼리 그룹을 짓는다고 생각해봅시다. 

SumArr[i] = (Arr[i] + SumArr[i-1]) % M;

범위	(1,1)	(1,2)	(1,3)	(1,4)	(1,5)
Sum	1	3	6	7	9
Sum Arr	1	0	0	1	0

2. 두 부분합의 차이는 곧 특정 구간의 합이 되므로,

Arr[i] ~ Arr[j] == SumArr[j] - SumArr[i-1]

3. 부분합을 M으로 나눈 나머지가 같은 그룹에서 

나머지 그룹	0	(1,2), (1,3), (1,5)
	1	(1,1), (1,4)

4. 두 부분합 A, B를 뽑으면, 그 두 부분합이 나타내는 연속된 구간합 (B-A)를 M으로 나눈 나머지는 0이 됩니다.

나머지 그룹 0	[(1,2), (1,3)] = (3)	[(1,2), (1,5)] = (3~5)	[(1,3), (1,5)] = (4~5)
{구간 값}, 구간 합	{3} , sum = 3	{3,1,2} , sum = 6	{1.2} ,sum = 3

나머지 그룹 1	[(1,1), (1,4)] = (2~4)
{구간 값}, 구간 합	{2, 3, 1} , sum = 6

 

정리하면, 우리의 목표는 M을 나눈 값의 누적합을 구하는 것.

기존 누적합(Arr[A] ~ Arr[B])을 구하는 하려면 (Sum[B] ~ Sum[A-1])

즉, (Sum[B] - Sum[A-1]) % M = 0 이 되는 쌍의 갯수이다. 

이 공식을 분배 법칙을 적용하면 (Sum[B]%M) = (Sum[A-1]%M).

마지막으로 서로다른 n개(부분합) 중에 r개(2개)를 선택하는 경우의 수 조합 nCr을 적용한다. 

 

이해하는데 오~~래 걸렸다.. 

만약 보시는 분 있다면 도움이 되었으면 좋겠습니다. ^^

---

※ 맞은 답