오류 정정
시간 제한2초메모리 제한256 MB
길이 n(최대 34)의 수신 비트열과 목표 다항 해시가 주어질 때, 해밍 거리가 최소이고 해시가 일치하는 비트열을 찾아 뒤집힌 비트 위치를 출력한다.
문제
통신 채널로 정보 메시지를 전송할 때 종종 오류가 발생하여 받은 메시지가 보낸 메시지와 달라진다. 이를 해결하기 위해 다양한 오류 검출 코드와, 가장 발생하기 쉬운 오류를 정정할 수 있는 정정 코드를 사용한다. 오류를 검출하는 방법 중 하나는 메시지와 함께 어떤 해시, 즉 체크섬을 전송하는 것이다. 받은 메시지에 대해 체크섬을 계산하여 원래 메시지의 체크섬과 비교할 수 있다.
이 문제에서는 다항식 해시로 계산되는 체크섬을 이용하여 받은 메시지의 오류를 정정하는 프로그램을 작성해야 한다. 전송되는 것은 n비트의 이진수로 저장된 비트 문자열이라고 하자. 비트를 최하위 비트부터 0으로 번호를 매기면, 다항식 해시는 다음 공식으로 계산된다.
h(a) = (a0 + a1t + a2t 2 + ... + a**i t i + ... + a**n − 1t n − 1) mod M, 여기서 a**i는 수의 i번째 비트이다.
이 문제에서 항상 t = 239, M = 109 + 7이다.
수신 측은 오염되었을 수 있는 메시지와, 보낸 메시지에 대해 계산된 다항식 해시를 받는다. 해시 자체는 오류 없이 전송된다고 가정한다. 오류 정정은 최대 우도 방법으로 이루어진다. 즉, 받은 메시지와 최소 개수의 비트에서 다른 메시지 중 해시가 받은 해시와 같은 것을 찾아야 한다.
입력
첫째 줄에는 전송된 메시지의 수 K (1 ≤ K ≤ 10)가 주어진다. 다음 K개 줄 각각에는 전송된 메시지의 설명이 주어진다. 세 정수 n (1 ≤ n ≤ 34)은 메시지의 길이, m (0 ≤ m < 2n )은 이진 표기가 받은 메시지의 비트 문자열을 나타내는 수, h (0 ≤ h < 109+7)는 받은 해시이다.
한 테스트에서 모든 전송된 메시지의 총 길이는 100을 넘지 않는다.
출력
각 메시지에 대해 별도의 줄에, 그 메시지를 해독할 수 없으면 정수 «−1»을 출력한다. 그렇지 않으면 먼저 수 d, 즉 최소 오류 개수를 출력하고, 같은 줄에 d개의 수, 즉 전송 중에 왜곡된 비트의 번호를 출력한다. 가능한 답이 여러 개이면 아무거나 출력한다.