7321: CodeChef DISJOINTXOR - Disjoint XOR
[Creator : ]
Description
Chef has a binary string $S$ of length $N$. Chef wants to find two disjoint substrings of equal length, such that their bitwise XOR is maximised.
Formally, Chef wants to find $L_1, R_1, L_2$, and $R_2$ such that:
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
Formally, Chef wants to find $L_1, R_1, L_2$, and $R_2$ such that:
- $1 \le L_1 \le R_1 \lt L_2 \le R_2 \le N$, that is, the substrings are disjoint (have no common elements);
- $|R_1 - L_1 + 1| = |R_2 - L_2 + 1|$, that is, the substrings have equal length;
- $S_{L_1 \dots R_1} \oplus S_{L_2 \dots R_2}$ is maximised, where $\oplus$ is the bitwise XOR operation.
Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.
Input
The first line of input will contain a single integer $T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer $N$ denoting the length of string $S$.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer $N$ denoting the length of string $S$.
The second line of each test case contains a binary string S of length N containing 0s and 1s only.
Output
For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module $10^9+7$.
Constraints
$1≤T≤10^5$
$2 \leq N \leq 5000$
S contains 0 and 1 only.
The sum of $N^2$ over all test cases won't exceed $2.5 \cdot 10^7$.
$2 \leq N \leq 5000$
S contains 0 and 1 only.
The sum of $N^2$ over all test cases won't exceed $2.5 \cdot 10^7$.
Sample 1 Input
3
4
1001
5
11111
3
011
Sample 1 Output
3
0
1
Test case 1: We can choose $L_1 = 1, R_1 = 2, L_2 = 3$, and $R_2 = 4$. Thus, the chosen substrings are 10 and 01. The XOR of these substrings is 11 whose decimal equivalent is 3.
Test case 2: We can choose $L_1 = 2, R_1 = 2, L_2 = 4$, and $R_2 = 4$. Thus, the chosen substrings are 1 and 1. The XOR of these substrings is 0 whose decimal equivalent is 0.
Test case 3: We can choose $L_1 = 1, R_1 = 1, L_2 = 3$, and $R_2 = 3$. Thus, the chosen substrings are 0 and 1. The XOR of these substrings is 1 whose decimal equivalent is 1.
Test case 2: We can choose $L_1 = 2, R_1 = 2, L_2 = 4$, and $R_2 = 4$. Thus, the chosen substrings are 1 and 1. The XOR of these substrings is 0 whose decimal equivalent is 0.
Test case 3: We can choose $L_1 = 1, R_1 = 1, L_2 = 3$, and $R_2 = 3$. Thus, the chosen substrings are 0 and 1. The XOR of these substrings is 1 whose decimal equivalent is 1.