KPart
시간 제한2초메모리 제한1024 MB
배열의 모든 연속 부분 배열 길이 K에 대해 두 부분의 합이 같도록 나눌 수 있는 K 값을 모두 찾습니다.
문제
Virgil은 배열의 성질을 연구하기 시작했다. 양의 정수로 이루어진 배열 에서, 길이가 인 모든 연속 부분 수열을 합이 같은 두 개의 서로소 부분 수열로 나눌 수 있으면, 를 -배열이라고 정의한다. 두 부분 수열은 연속일 필요가 없다. 예를 들어 1, 2, 1, 3은 3-배열이다. 1, 2, 1은 1, 1과 2로 나눌 수 있고 두 합이 모두 2이다. 2, 1, 3은 2, 1과 3으로 나눌 수 있고 두 합이 모두 3이다. 1, 2는 합이 같은 두 부분 수열로 나눌 수 없으므로 2-배열이 아니다. 4-배열도 아니다.
입력
첫 줄에 정수 가 주어진다. 이어서 개의 배열이 주어진다. 각 배열은 두 줄로 나타낸다. 첫 줄에는 배열의 길이 이, 둘째 줄에는 배열의 원소들이 공백 하나로 구분되어 주어진다.
출력
각 배열 에 대해 입력 순서대로 한 줄씩 출력한다. 한 줄에는 가 -배열이 되는 의 개수를 먼저 쓰고, 이어서 그 값들을 오름차순으로 쓴다.
제한
.
는 한 배열 원소들의 합이다(모든 배열의 합이 아니다). 이때 이다.
힌트
길이가 7인 첫 번째 배열은 길이 4와 길이 6의 연속 부분 수열이 각각 합이 같은 두 개의 (연속이 아닐 수도 있는) 부분 수열로 나뉘므로 4-배열이자 6-배열이다.
길이가 6인 두 번째 배열은 길이 3의 연속 부분 수열과 길이 6의 연속 부분 수열이 각각 합이 같은 두 개의 (연속이 아닐 수도 있는) 부분 수열로 나뉘므로 3-배열이자 6-배열이다.