원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
XOR 최대
원제: XOR 최대
문제
어떤 문자열에서 연속한 위치에 있는 1개 이상의 문자를 선택해 순서를 유지한 채로 나열해서 얻을 수 있는 문자열을 그 문자열의 부분문자열이라 한다. 예를 들어, 는 의 부분문자열이지만, 의 부분문자열은 아니다.
음이 아닌 두 정수 의 배타적 논리합 는 다음과 같이 정의된다.
- 이진법으로 생각했을 때, 의 의 자릿수와 의 의 자릿수가 서로 다르면 의 의 자릿수가 이고, 같으면 의 의 자릿수가 이다. (단, )
- 예를 들어 은 이므로 이다.
과 로만 구성된 길이가 인 문자열 가 주어진다.
당신은 의 부분문자열 를 선택해서 만들 수 있는 의 최댓값을 계산해야 한다. 는 다음과 같이 정의되는 함수이다:
- 의 부분문자열 에 대해, 의 값은 를 이진법으로 해석했을 때의 값이다. 예를 들어, 만약 이면 이다.
- 는 과 의 배타적 논리합이다.
이때 과 가 서로 다를 필요는 없다. 즉, 과 는 에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.
과 로만 구성된 문자열 가 주어지면, 가능한 의 최댓값을 구하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 모든 테스트 케이스에서 의 합
- 는 과 로만 이루어진 길이가 인 문자열이다.
부분문제
- (17점) , 모든 테스트 케이스에서 의 합
- (20점) , 모든 테스트 케이스에서 의 합
- (13점) , 모든 테스트 케이스에서 의 합
- (12점) , 모든 테스트 케이스에서 의 합
- (38점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스마다, 첫 번째 줄에 문자열의 길이 , 두 번째 줄에 과 로만 구성된 길이가 인 문자열 가 주어진다.
출력 형식
각 테스트 케이스마다 가능한 의 최댓값을 이진법으로 한 줄에 하나씩 출력한다. 단, 정답 앞에 필요 없는 은 출력하지 않는다.
예제
예제 1
4 3 010 5 10101 5 00100 5 11111
11 11111 110 11110
첫 번째 테스트 케이스에서 , 로 설정하면 을 만들 수 있다. 대신 으로도 표현할 수 있지만, 정답 앞에 필요 없는 을 출력하면 안 되므로 이 아닌 을 출력해야 한다.
네 번째 테스트 케이스에서 , 로 설정하면 을 만들 수 있다.
예제 2
4 2 00 2 01 2 10 2 11
0 1 11 10