310664: CF1867B. XOR Palindromes
Description
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), then the string $s$ becomes a palindrome.
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.
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.
InputEach 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.
The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).
The second line of each test case contains a binary string $s$ of length $n$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output a single line containing a binary string $t$ of length $n+1$ - the answer to the problem.
ExampleInput5 6 101011 5 00000 9 100100011 3 100 1 1Output
0010100 111111 0011111100 0110 11Note
Consider the first example.
- $t_2 = 1$ because we can choose $l = $ 010100, then the string $s$ becomes 111111, which is a palindrome.
- $t_4 = 1$ because we can choose $l = $ 101011.
- It can be shown that for all other $i$, there is no answer, so the remaining symbols are $0$.
Output
给定一个长度为n的只包含0和1的字符串s。如果存在一个长度为n的包含x个1的字符串l，使得将s的每个字符s_i用s_i XOR l_i（其中XOR表示按位异或操作）替换后，字符串s变成一个回文串，则称数字x是好的。需要输出一个长度为n+1的字符串t，其中t_i（0≤i≤n）等于1如果数字i是好的，否则等于0。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数n（1≤n≤10^5）。
- 第二行包含一个长度为n的二进制字符串s。
- 保证所有测试用例的n之和不超过10^5。
输出：
- 对于每个测试用例，输出一行长度为n+1的二进制字符串t，作为问题的答案。
示例：
输入：
```
5
6
101011
5
00000
9
100100011
3
100
1
1
```
输出：
```
0010100
111111
0011111100
0110
11
```
注意：
- 考虑第一个例子，t_2 = 1因为可以选择l = 010100，然后字符串s变成111111，它是一个回文串。
- t_4 = 1因为可以选择l = 101011。
- 可以证明对于所有其他i，没有答案，所以剩余的符号是0。题目大意： 给定一个长度为n的只包含0和1的字符串s。如果存在一个长度为n的包含x个1的字符串l，使得将s的每个字符s_i用s_i XOR l_i（其中XOR表示按位异或操作）替换后，字符串s变成一个回文串，则称数字x是好的。需要输出一个长度为n+1的字符串t，其中t_i（0≤i≤n）等于1如果数字i是好的，否则等于0。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^5），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数n（1≤n≤10^5）。 - 第二行包含一个长度为n的二进制字符串s。 - 保证所有测试用例的n之和不超过10^5。 输出： - 对于每个测试用例，输出一行长度为n+1的二进制字符串t，作为问题的答案。 示例： 输入： ``` 5 6 101011 5 00000 9 100100011 3 100 1 1 ``` 输出： ``` 0010100 111111 0011111100 0110 11 ``` 注意： - 考虑第一个例子，t_2 = 1因为可以选择l = 010100，然后字符串s变成111111，它是一个回文串。 - t_4 = 1因为可以选择l = 101011。 - 可以证明对于所有其他i，没有答案，所以剩余的符号是0。