1867B.md (1832B)
1 Source: https://codeforces.com/problemset/problem/1867/B 2 3 B. XOR Palindromes 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary string $s$ of length $n$ (a string that consists only of $0$ and $1$). A number $x$ is good if there exists a binary string $l$ of length $n$, containing $x$ ones, such that if each symbol $s_i$ is replaced by $s_i \oplus l_i$ (where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)), then the string $s$ becomes a palindrome. 22 23 You need to output a binary string $t$ of length $n+1$, where $t_i$ ($0 \leq i \leq n$) is equal to $1$ if number $i$ is good, and $0$ otherwise. 24 25 A palindrome is a string that reads the same from left to right as from right to left. For example, 01010, 1111, 0110 are palindromes. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows. 30 31 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$). 32 33 The second line of each test case contains a binary string $s$ of length $n$. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, output a single line containing a binary string $t$ of length $n+1$ - the answer to the problem. 40 41 Example 42 43 Input 44 45 ``` 46 5 47 48 6 49 50 101011 51 52 5 53 54 00000 55 56 9 57 58 100100011 59 60 3 61 62 100 63 64 1 65 66 1 67 ``` 68 69 Output 70 71 ``` 72 0010100 73 111111 74 0011111100 75 0110 76 11 77 ``` 78 79 Note 80 81 Consider the first example. 82 83 * $t_2 = 1$ because we can choose $l = $ 010100, then the string $s$ becomes 111111, which is a palindrome. 84 * $t_4 = 1$ because we can choose $l = $ 101011. 85 * It can be shown that for all other $i$, there is no answer, so the remaining symbols are $0$.