Math Encoder

면접 대비

시간 제한20초메모리 제한1024 MB

요약

정렬된 수열에서 모든 비어 있지 않은 부분집합의 최댓값과 최솟값의 차이를 모두 더해 1000000007로 나눈 나머지를 구한다.

문제

Math 교수는 비밀 프로젝트를 진행하던 중, 숫자 목록을 하나의 숫자로 가장 효율적으로 인코딩해야 하는 문제에 부딪혔다. 오랜 연구 끝에 Math 교수는 숫자를 인코딩하는 가장 좋은 3단계 과정을 찾아냈다.

첫 번째 단계는 숫자 목록의 모든 공집합이 아닌 부분집합을 찾고, 각 부분집합에서 가장 큰 수와 가장 작은 수의 차이(가장 큰 수에서 가장 작은 수를 뺀 값)를 구하는 것이다. 부분집합에 숫자가 하나만 있으면 그 숫자가 가장 큰 수이자 가장 작은 수이다. 전체 집합 자체도 부분집합으로 본다.
그런 다음 모든 차이를 더해 최종 인코딩된 숫자를 얻는다.
숫자가 클 수 있으므로 109 + 7 (1000000007)로 나눈 나머지를 출력한다.

교수는 아래에 예시와 그 설명을 공유했다. 숫자 목록이 주어졌을 때, 최종 인코딩된 숫자를 계산하는 효율적인 함수를 만드는 것을 도와줄 수 있는가?

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 2개의 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 최종 인코딩된 숫자이다.

출력이 매우 클 수 있으므로 결과를 소수 109 + 7 (1000000007)로 나눈 나머지만 출력하면 된다.