Minimal String Xoration
有点智慧但不是特别智慧反正是我达不到的智慧。
打表可以看出长度为 \(2^x\) 的 \(i\oplus k\) 出现次数为 \(2^{n-k}\)。
进一步发现,设 \(f(k,x)\) 当前选取 k 时,数列前 \(2^k\) 的下标。
则 \(f(k,x)=f(k,x-1)+f(k\oplus{2^{x-1}},x-1)\)
因为对于 \(p\in[0,2^{x-1})\),\(p\oplus k=(p+2^{x-1})\oplus(k+2^{x-1})\)
所以就可以倍增求出每个 k 对应的序列,使用 Hash 就可以直接倍增做了。
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ull unsigned long long
const int N=20;
const int MAXN=262146;
const ull bas1=20061103;
const ull bas2=1145141;
int n,m,a[MAXN],m1[MAXN],m2[MAXN];
string s;
ull p1[MAXN][N],p2[MAXN][N];
int check(int x,int y){
if(p1[x][n]==p1[y][n]&&p2[x][n]==p2[y][n]) return 0;
for(int i=n-1;~i;i--){
if(p1[x][i]==p1[y][i]&&p2[x][i]==p2[y][i]) x^=(1<<i),y^=(1<<i);
}
return a[x]<a[y]?-1:1;
}
int main(){
cin>>n;m=1<<n;
m1[0]=1;m2[0]=1;
for(int i=1;i<m;i++) m1[i]=m1[i-1]*bas1,m2[i]=m2[i-1]*bas2;
cin>>s;
for(int i=0;i<m;i++) a[i]=s[i]-'a'+1;
for(int i=0;i<m;i++) p1[i][0]=p2[i][0]=a[i];
for(int j=1;j<=n;j++){
for(int i=0;i<m;i++){
p1[i][j]=p1[i][j-1]*m1[1<<(j-1)]+p1[i^(1<<(j-1))][j-1];
p2[i][j]=p2[i][j-1]*m2[1<<(j-1)]+p2[i^(1<<(j-1))][j-1];
}
}
int res=0;
for(int i=1;i<m;i++){
if(check(i,res)==-1) res=i;
}
for(int i=0;i<m;i++) cout<<s[i^res];
return 0;
}