어떤 문자열에서 연속한 위치에 있는 \(1\)개 이상의 문자를 선택해 순서를 유지한 채로 나열해서 얻을 수 있는 문자열을 그 문자열의 부분문자열이라 한다. 예를 들어, \(001\)는 \(X = 10011\)의 부분문자열이지만, \(Y = 10101\) 의 부분문자열은 아니다.
  음이 아닌 두 정수 \(A, B\)의 배타적 논리합 \(A ⊕ B\)는 다음과 같이 정의된다

• 이진법으로 생각했을 때, \(A\)의 \(2^k\)의 자릿수와 \(B\)의 \(2^k\)의 자릿수가 서로 다르면 \(A ⊕ B\)의 \(2^k\)의 자릿수가 \(1\)이고, 같으면 \(A ⊕ B\)의 \(2^k\)의 자릿수가 \(0\)이다. (단, \(k \ge 0\))
• 예를 들어 \(12 ⊕ 10\)은 \(12 = 1100_{(2)}, 10 = 1010_{(2)}\)이므로 \(1100_{(2)} ⊕ 1010_{(2)} = 0110_{(2)} = 6\)이다. 

\(0\)과 \(1\)로만 구성된 길이가 \(N\)인 문자열 \(S\)가 주어진다. 
당신은 \(S\)의 부분문자열 \(s1, s2\)를 선택해서 만들 수 있는 \(g(s1, s2)\)의 최댓값을 계산해야 한다. \(g(s1, s2)\)는 다음과 같이 정의되는 함수이다:

• \(S\)의 부분문자열 \(s\)에 대해, \(f(s)\)의 값은 \(s\)를 이진법으로 해석했을 때의 값이다. 예를 들어, 만약 \(s = 11010\)이면 \(f(s) = 26\)이다.
• \(g(s1, s2)\)는 \(f(s1)\)과 \(f(s2)\)의 배타적 논리합이다.

이때 \(s1\)과 \(s2\)가 서로 다를 필요는 없다. 즉, \(s1\)과 \(s2\)는 \(S\)에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.
\(0\)과 \(1\)로만 구성된 문자열 \(S\)가 주어지면, 가능한 \(g(s1, s2)\)의 최댓값을 구하는 프로그램을 작성하라.

제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le T \le 100\)
• \(2 \le N \le 10^7\)
• 모든 테스트 케이스에서 \(N\)의 합 \(\le 10^7\)
• \(S\)는 \(0\)과 \(1\)로만 이루어진 길이가 \(N\)인 문자열이다.

부분문제
1. (17점) \(N \le 30\), 모든 테스트 케이스에서 \(N\)의 합 \(\le 300\)
2. (20점) \(N \le 200\), 모든 테스트 케이스에서 \(N\)의 합 \(\le 2000\)
3. (13점) \(N \le 3 000\), 모든 테스트 케이스에서 \(N\)의 합 \(\le 30 000\)
4. (12점) \(N \le 2 \times 10^5\) , 모든 테스트 케이스에서 \(N\)의 합 \(\le 2 \times 10^6\)
5. (38점) 추가 제약 조건 없음

첫 번째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.
각 테스트 케이스마다, 첫 번째 줄에 문자열의 길이 \(N\), 두 번째 줄에 \(0\)과 \(1\)로만 구성된 길이가 \(N\)인 문자열 \(S\)가 주어진다.

각 테스트 케이스마다 가능한 \(g(s1, s2)\)의 최댓값을 이진법으로 한 줄에 하나씩 출력한다. 단, 정답 앞에 필요 없는 \(0\)은 출력하지 않는다.

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2024KOI2차