레이팅 미적용길이 \(N\)의 비트 문자열 \(s_{1\dots N}\) (\(2\le N\le 10^9\))이 주어진다. 한 번의 연산으로, 다음 조건이 모두 참이면 구간 \(s_{l\dots r}\)을 뒤집을 수 있다.
- 구간의 크기가 짝수이다.
- 구간의 앞쪽 절반은 한 종류의 문자(\(0\) 또는 \(1\))로 이루어지고, 뒤쪽 절반은 반대 문자로 이루어진다.
- \(l = 1\)이거나 \(s_{l-1} \neq s_l\)이다.
- \(r = N\)이거나 \(s_{r+1} \neq s_r\)이다.
모든 \(1\)을 맨 앞으로 옮기기 위한 최소 연산 횟수를 구하거나, 불가능함을 보고하시오. 가능하다면, 이 최솟값을 달성하는 연산 수열의 개수도 \(10^9+7\)로 나눈 나머지로 출력한다.
문제 제공: Sujay Konda
채점 방식
- 입력 3: \(N \leq 10\), 모든 테스트가 서로 다르다
- 입력 4: \(R\le 10\)
- 입력 5-8: \(R\le 100\), 모든 테스트에 대한 \(R^2\)의 합이 \(10^5\)를 넘지 않으며, 최소 연산 횟수가 \(R/2-1\)과 같음이 보장된다.
- 입력 9-12: \(R\le 100\), 모든 테스트에 대한 \(R^2\)의 합이 \(10^5\)를 넘지 않는다.
- 입력 13-16: 추가 제약 조건이 없다.
문제 제공: Sujay Konda
첫째 줄에 독립적인 테스트의 수 \(T\) (\(1 \leq T \leq 2026\))가 주어진다. 각 테스트는 다음 형식으로 주어진다.
비트 문자열은 압축된 형식으로 주어진다. 첫째 줄에 문자열의 런 수 \(R\) (\(2\le R\le 800\))와 문자열의 첫 문자(0 또는 1)가 주어진다.
다음 줄에 \(s\)에서 같은 문자로 이루어진 극대 연속 블록들의 길이인 \(R\)개의 정수 \(l_1,l_2,l_3,\ldots l_R\) (\(0
추가로, 모든 테스트에 대한 \(R^2\)의 합은 \(1.5\cdot 10^6\)을 넘지 않음이 보장된다.
각 테스트 케이스마다, 모든 \(1\)을 맨 앞으로 옮기기 위한 최소 연산 횟수를 출력하거나 불가능하면 \(-1\)을 출력하고, 이 최솟값을 달성하는 연산 수열의 개수를 \(10^9+7\)로 나눈 나머지로 함께 출력한다.
9
2 0
1 1
2 1
1 1
2 1
2 1
2 0
1 2
5 0
1 1 1 2 1
3 0
1 2 1
8 0
1 1 2 1 1 2 1 1
6 0
3 3 1 2 2 1
7 0
5 1 1 3 2 1 11 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1Here is the sequence of two operations for the fifth testcase:
\(010110 \to 100110 \to 111000.\)
5
2 1
1 1
4 1
1 1 1 1
6 1
1 1 1 1 1 1
8 1
1 1 1 1 1 1 1 1
10 1
1 1 1 1 1 1 1 1 1 10 1
1 1
2 1
3 3
4 9In all of these test cases, the minimum number of operations equals \(R/2-1\).
Here are all three possible sequences of three operations for the fourth test
case:
(1)
10101010
-> 11001010
-> 11001100
-> 11110000
(2)
10101010
-> 10110010
-> 10001110
-> 11110000
(3)
10101010
-> 10101100
-> 11001100
-> 11110000