Module: 중간에서 만나


Problem

1 /5


모듈로 최대 부분 수열

Theory Click to read/hide

중간 만남
Meet-in-the-middle - 최적화 방법 솔루션은 원래 문제를 두 부분으로 나누고 각각을 독립적으로 해결한 다음 두 부분의 솔루션을 결합하여 원래 문제에 대한 솔루션을 얻는 것으로 구성됩니다.

따라서 두 가지 조건이 충족되면 meet-in-the-middle을 사용하는 것이 좋습니다.
1) 문제의 절반을 해결하는 데 필요한 시간은 전체 문제를 해결하는 데 걸리는 시간보다 점근적으로 적습니다.
2) 절반의 문제를 풀면 원래의 전체 문제에 대한 해결책을 얻을 수 있으며 동시에 전체 문제를 푸는 것보다 점근적으로 더 빠릅니다.
 
예시
정수 A, B, C 및 D의 네 가지 배열이 있다고 가정합니다. 이러한 숫자의 합이 0이 되도록 각 배열에서 정확히 하나의 숫자를 선택해야 합니다. 순진한 솔루션을 사용할 수 있습니다. 즉, 가능한 모든 옵션을 간단히 열거하는 것입니다. 이것은 O(n4)에서 작동합니다.

그러나 meet-in-the-middle을 사용할 수 있습니다.
a + b + c + d = 0은 (a + b) = -(c + d)와 같습니다.
작업을 두 부분으로 나누겠습니다. 즉, 전반부에서는 배열 A 및 B만 사용하고 후반부에서는 C 및 <코드 >D.
전반부에 가능한 모든 (a + b) 옵션을 반복하고 모든 값을 해시 테이블(unordered_map, HashMap 등). 이것은 O(n2)에서 작동합니다.
이제 우리는 후반부에서 가능한 모든 옵션 (c + d)에 대해 반복할 것입니다. 특정 옵션을 고려할 때 반대 기호의 현재 합과 연결된 해시 테이블에 값이 있는지 확인합니다(그런 다음 합이 0이 되는 두 개의 역수를 찾았습니다). 이 부분은 O(n2)에서도 작동합니다.
여기에는 별도의 "답변 병합" 단계가 없습니다. 하나에서, 우리는 각 절반을 해결하는 과정에서 이것을 했습니다. 대부분의 작업은 비슷한 상황을 겪게 됩니다.
우리는 meet-in-the-middle을 사용하여 O(n2)에서 해결책을 찾았습니다.

meet-in-the-middle은 실행 시간에 상당한 영향을 미치는 기하급수적 솔루션을 최적화할 때 가장 자주 사용된다는 점은 주목할 가치가 있습니다.

Problem

n 양의 정수와 숫자 m로 구성된 배열 A가 주어집니다. 위치 의 순서를 선택하십시오. B 1, B2, ..., Bk (1 <= B1 2 k <= n)   ; \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) 최대값(즉, 따라서  서브시퀀스의 요소 합계를 숫자 m 로 나눈 나머지가 가능한 최대값입니다.) 선택한 시퀀스는 비어 있을 수 있습니다.
\((\sum_{i=1}^{k} A_{B_i}) mod \; m\)의 가능한 최대값을 계산합니다.

입력
첫 번째 줄에는 두 개의 정수 n 및 m이 포함됩니다(1 <= n <= 35, 1 <= m <= 109). 두 번째 줄에는 n개의 정수 A1, A2, ..., An (1 <= Ai <= 109 )< br />
출판물
하나의 숫자 출력 - 최대값 \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 
예
<헤드> <몸>  
설명
첫 번째 예에서 B = {1, 2}를 선택할 수 있습니다. (A1 + A2) mod m = (5 + 2) % 4 = 3.
두 번째 예에서는 B = {3}를 선택할 수 있습니다.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# 입력 출력
1 4 4
5 2 4 1 		3
2 3 20
199 41 299 		19