这里是一个关于 \(n\) 的奇偶性分类讨论的做法。
设最终的答案序列为 \(\{ans_{n+1}\}\)，它由 \(0,1\) 组成。
首先计算出原序列中有序数对 \((i,n-i+1)\) 的个数，使得 \(s_i \not= s_{n-i+1}\)。记这个数为 \(cnt\)，显然 \(cnt \le \lfloor\dfrac{n}{2}\rfloor\)。
此时容易解决 \(n\) 为奇数的情况。结论是：对于 \(i \in [cnt,n-cnt]\)，\(ans_i=1\)，否则 \(ans_i=0\)。
因为只需要让原本不匹配的 \(cnt\) 对位置匹配。对于 \(i>cnt\)，如果 \(i-cnt\) 为偶数，则可以让原本匹配的两个位置上的数同时取异或，显然这样仍然匹配。否则，可以让整个序列的中点上的数取异或，这样不影响其他位置，剩下的就与 \(i-cnt\) 为偶数时相同。
但对于 \(i>n-cnt\)，上面的策略就不适用了。因为此时必然会将已经匹配好的一对位置变得不再匹配。
类比之前的做法，考虑 \(n\) 为偶数的情况。
注意到 \(n\) 为偶数与 \(n\) 为奇数最大的区别就是没有了中间点，因此除开必须改变的 \(cnt\) 对位置上的数，改变的数的数量必须为偶数。这相当于 \(\forall i \in [cnt,n-cnt],i-cnt\) 为偶数。这又等价于在区间 \([cnt,n-cnt]\) 中，\(ans\) 隔一个为 \(1\)。
于是在 \(\mathcal{O}(n)\) 的时间复杂度内解决了问题。
代码：
#include<bits/stdc++.h>
using namespace std;
bool Mbegin;
namespace Fast_In_Out{
char buf[1<<21],*P1=buf,*P2=buf;
#define gc getchar()
int read(){
int f=1,x=0;
char c=gc;
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=gc;
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=gc;
}
return f*x;
}
void write(int x){
if(x<0)
x=-x,putchar('-');
if(x>9)
write(x/10);
putchar(x%10+'0');
}
#undef gc
}
using namespace Fast_In_Out;
const int N=1e5+8;
int n;
char str[N];
namespace odd{
bool ans[N];
void solve(){
for(int i=0;i<=n;i++)
ans[i]=0;
int cnt=0;
for(int i=1;i<=n/2;i++)
if(str[i]!=str[n-i+1])
cnt++;
for(int i=cnt;i<=n-cnt;i++)
ans[i]=1;
for(int i=0;i<=n;i++)
write(ans[i]);
putchar('\n');
}
}
namespace even{
bool ans[N];
void solve(){
for(int i=0;i<=n;i++)
ans[i]=0;
int cnt=0;
for(int i=1;i<=n/2;i++)
if(str[i]!=str[n-i+1])
cnt++;
for(int i=cnt;i<=n-cnt;i+=2)
ans[i]=1;
for(int i=0;i<=n;i++)
write(ans[i]);
putchar('\n');
}
}
void solve(){
n=read();
scanf("%s",str+1);
if(n%2==1)
odd::solve();
else
even::solve();
}
bool Mend;
int main(){
fprintf(stderr,"%.3lf MB\n\n\n",(&Mbegin-&Mend)/1048576.0);
int testnum=read();
while(testnum--)
solve();
fprintf(stderr,"\n\n\n%.0lf ms",1e3*clock()/CLOCKS_PER_SEC);
return 0;
}