양의 정수로 이루어진 길이 의 배열 이 주어진다.
배열에서 원소를 하나 이상 골라, 원래 순서대로 나열한 부분수열 를 만든다. 선택한 부분수열에 다음 연산을 원하는 만큼 수행할 수 있다.
예를 들어 에서 를 선택하면 가 된다. 만 나누고 은 그대로 두는 것은 허용되지 않는다. 연산의 영향을 받을 원소를 따로 선택할 수 없기 때문이다.
이 연산으로 의 모든 원소를 같은 값으로 만들려고 한다. 만들 수 있는 공통 값 중 가장 큰 값을 라고 하자. 연산을 한 번도 하지 않아도 되며, 모든 원소를 로 만드는 것은 항상 가능하다.
예를 들어 이면 을 선택하여 으로 만든 뒤, 를 선택하여 로 만들 수 있다. 이때 만들 수 있는 가장 큰 공통 값은 이므로 이다. 원소가 하나인 부분수열에서는 아무 연산도 하지 않는 것이 가장 좋으므로 이다.
모든 비어 있지 않은 부분수열 에 대한 의 합을 으로 나눈 나머지를 구하여라.
각 부분수열은 원래 값에서 독립적으로 시작한다. 한 부분수열에 수행한 연산이 다른 부분수열에 영향을 주지는 않는다. 또한 선택한 인덱스가 다르면 값이 같아도 서로 다른 부분수열로 센다. 예를 들어 에서 비어 있지 않은 부분수열은 첫 번째 원소만 고른 , 두 번째 원소만 고른 , 두 원소를 모두 고른 의 세 개이다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 모든 비어 있지 않은 부분수열 에 대한 의 합을 으로 나눈 나머지를 한 줄에 출력한다.
각 테스트 케이스에서 이라고 하자.
원소 하나를 고른 세 부분수열의 기여는 각각 이다. 에서는 으로 나누어 을 만들고, 로 나누어 를 만들 수 있어 최댓값이 이다. , , 의 최댓값은 모두 이다. 따라서 답은 이다.
첫째 줄에 테스트 케이스의 수 가 주어진다. 각 케이스는 다음과 같은 형식으로 주어진다.
각 케이스의 첫째 줄에 배열의 길이 이 주어진다. 둘째 줄에 배열의 원소 개가 공백으로 구분되어 주어진다.
| 3 | 19 | 모든 는 square-free이다. 즉, 어떤 소수 에 대해서도 이 를 나누지 않는다. |
| 4 | 24 | 각 테스트 케이스에서 , 이다. 모든 테스트 케이스에 대한 의 합과 의 합이 각각 이하이다. |
| 5 | 37 | 추가적인 제약이 없다. |
첫 번째 케이스에서는 서로 다른 인덱스 선택으로 얻는 부분수열이 세 개이고 모두 이므로 답은 이다. 두 번째 케이스에서 에 를 고르는 연산을 반복하면 , , 이 된다. 두 원소를 같은 값으로 만들 수 있는 최댓값은 이므로 답은 이다. 세 번째 케이스에서는 비어 있지 않은 부분수열 개가 모두 을 기여한다.
