A-E 都还是比较简单的。
首先，容易想到的，异或上 \(2^k\)，相当于以 \(2^{k+1}\) 的长度分块，然后每一块对半切，然后交换左右部分。
我的想法是由于这个交换的性质，也许我们可以尝试着快速计算哈希值。
显然有 \(h(x,2^k,i)=h(x,2^{k-1},i)+h(x \ \text{xor} \ 2^{k-1},2^{k-1},i)\)，\(h(x,k,i)\) 表示异或上 \(x\)，长度为 \(2^k\)，左端点为 \(i\)，这个区间的哈希值。
不过你现在好像必须 \(O(n^2)\) 以上取计算每个状态！
于是你考虑能否交换，使得查询区间成为前缀区间，然后我们只记录前缀区间的哈希值即可。
显然你可以写一份暴力，每次判断查询区间是否与 0 分居两侧，是的话就换。写出来后发现 \(x=x\ \text{xor} \ i\) 即可。
#pragma GCC optimize("Ofast","-funroll-loops")
#pragma GCC target("sse4.1","sse4.2","ssse3","sse3","sse2","sse","avx2","avx","popcnt","tune=native")
#include <bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define pb push_back
using namespace std;
const ull base=19260817;
const int N=(1<<18)+5;
//map<int,ull>mp[N][19];
ull h[N][19];
ull v[26],pw[N];
char s[N];
int n,m,M;
mt19937 RAND(time(0));
ull cal(ull x) {
return x*x*x*x+2*x*x*x+3*x*x+4*x+7+M;
}
ull dfs(int x,int k,int i) { //i\to 0
// for(int t=1;t<=m+1;t++) {
// for(int p=m;p>=0;p--) {
// int l=(1<<p),r=(1<<(p+1))-1;
//// if(l<=i&&(i+(1<<k)-1)<=r) {
// if((i>>p)&1) {
// x^=(1<<p);
// i-=l;
// }
// }
x^=i;
// cout<<i<<" "<<h[x][k]<<'\n';
return h[x][k];
// }
}
ull get(int x,int l,int r) {
int qwq=(r-l+1),nw=l; ull res=0;
for(int i=m;i>=0;i--) {
// cout<<nw<<" "<<res<<" "<<l<<" "<<r<<'\n';
if((qwq>>i)&1) {
res=res*pw[(1<<i)]+dfs(x,i,nw);
nw+=(1<<i);
}
}
return res;
// ull res=0;
// for(int i=l;i<=r;i++) res=res*base+s[i^x]-'a';
// cout<<x<<" "<<l<<" "<<r<<" "<<res<<'\n';
// return res;
}
bool cmp(int x,int y) {
int l=0,r=n-1,res=-1;
while(l<=r) {
int mid=(l+r)>>1;
if(get(x,0,mid)==get(y,0,mid)) res=mid,l=mid+1;
else r=mid-1;
}
if(res==n-1) return 0;
++res;
// cout<<x<<" "<<y<<" "<<res<<" "<<s[res^x]<<" "<<s[res^y]<<'\n';
if(s[res^x]<s[res^y]) return 1;
return 0;
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>m>>s; n=(1<<m);
M=RAND()%10;
for(int i=0;i<26;i++) v[i]=cal(cal(cal(cal(cal((ull)i)))));
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base;
for(int i=0;i<n;i++) {
// for(int j=0;j<n;j++) {
// h[i][0][j]=v[s[j^i]-'a'];
// }
h[i][0]=v[s[i]-'a'];
}
for(int k=1;k<=m;k++) {
int len=(1<<k);
for(int x=0;x<n;x++) {
// for(int i=0;i<n;i+=len) {
// h[x][k][i]=h[x][k-1][i]*pw[len/2]+h[x^(1ll<<(k-1))][k-1][i];
// }
h[x][k]=h[x][k-1]*pw[len/2]+h[x^(1<<(k-1))][k-1];
}
}
int ans=0;
for(int i=1;i<n;i++) {
if(cmp(i,ans)==1)
// {
// for(int j=0;j<=m;j++) map<int,ull>().swap(mp[ans][j]);
ans=i;
// } else {
// for(int j=0;j<=m;j++) map<int,ull>().swap(mp[i][j]);
// }
}
// cout<<ans<<'\n';
for(int i=0;i<n;i++) cout<<(char)(s[i^ans]);
return 0;
}