아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

KPart

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

요약
배열의 모든 연속 부분 배열 길이 K에 대해 두 부분의 합이 같도록 나눌 수 있는 K 값을 모두 찾습니다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산, 슬라이딩 윈도우
정답자
아직 제출이 없습니다

문제

Virgil은 배열의 성질을 연구하기 시작했다. 양의 정수로 이루어진 배열 AA에서, 길이가 KK인 모든 연속 부분 수열을 합이 같은 두 개의 서로소 부분 수열로 나눌 수 있으면, AA를 KK-배열이라고 정의한다. 두 부분 수열은 연속일 필요가 없다. 예를 들어 1, 2, 1, 3은 3-배열이다. 1, 2, 1은 1, 1과 2로 나눌 수 있고 두 합이 모두 2이다. 2, 1, 3은 2, 1과 3으로 나눌 수 있고 두 합이 모두 3이다. 1, 2는 합이 같은 두 부분 수열로 나눌 수 없으므로 2-배열이 아니다. 4-배열도 아니다.

입력

첫 줄에 정수 TT가 주어진다. 이어서 TT개의 배열이 주어진다. 각 배열은 두 줄로 나타낸다. 첫 줄에는 배열의 길이 NN이, 둘째 줄에는 배열의 원소들이 공백 하나로 구분되어 주어진다.

출력

각 배열 AA에 대해 입력 순서대로 한 줄씩 출력한다. 한 줄에는 AA가 KK-배열이 되는 KK의 개수를 먼저 쓰고, 이어서 그 KK 값들을 오름차순으로 쓴다.

제한

1≤T≤201 \le T \le 20.

∑A\sum A는 한 배열 원소들의 합이다(모든 배열의 합이 아니다). 이때 1≤∑A≤1000001 \le \sum A \le 100000이다.

힌트

길이가 7인 첫 번째 배열은 길이 4와 길이 6의 연속 부분 수열이 각각 합이 같은 두 개의 (연속이 아닐 수도 있는) 부분 수열로 나뉘므로 4-배열이자 6-배열이다.

길이가 6인 두 번째 배열은 길이 3의 연속 부분 수열과 길이 6의 연속 부분 수열이 각각 합이 같은 두 개의 (연속이 아닐 수도 있는) 부분 수열로 나뉘므로 3-배열이자 6-배열이다.

예제1

  1. 예제 1

    입력
    2
    7
    7 3 5 1 3 3 5
    6
    1 2 3 5 8 3
    
    예상 출력
    2 4 6
    2 3 6