Codeforces Round #778 (Div. 1 + Div. 2)

F. Minimal String Xoration

题目描述

点此看题

解法

记 \(f(s,d)\) 为 \(t_i=s_{i\oplus d}\) 的字符串 \(t\)，可以将问题转化成：把 \(f(s,0),f(s,1)...f(s,2^n-1)\) 按照字典序从小到大排序，那么字典序最小的就是答案。

那么可以考虑类似后缀数组一样倍增，假设现在我们知道在 \(2^k\) 的前缀意义下，\(f(s,0\sim2^{n}-1)\) 的大小关系，我们考虑快速计算在 \(2^{k+1}\) 的前缀意义下 \(f(s,0\sim 2^{n}-1)\) 的大小关系。

设 \(rk[i]\) 表示 \(f(s,i)\) 的字典序排名，那么 \(f(s,i)\) 的特征可以用 \((rk[i],rk[i\oplus 2^k])\) 来表示，我们把这个二元组排序，然后生成新一轮的 \(rk\) 即可（思路本质上就是后缀数组的思路），时间复杂度 \(O(n^22^n)\)

#include 
#include 
#include 
#include 
using namespace std;
const int M = 1<<18;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,b[26],rk[M],sa[M],nw[M];char s[M];
signed main()
{
	n=1<