题意：给定一个长度为n(n<=150000)的字符串，每个下标i与(i*i+1)%n连边，求从任意下标出发走n步能走出的字典序最大的字符串。
把下标看成结点，由于每个结点有唯一的后继，因此形成的是内向基环树森林，相当于求基环树上字典序最大的路径。
实际上基环树和树一样是可以通过倍增得到走2^k步能走到的结点的，然后后缀数组又可以通过倍增求出长度为2^k的后缀的字典序，两者结合一下就可以对所有路径按字典序排序了。
复杂度$O(nlogn)$，感觉这应该是标解吧，不过由于数据可能比较随机因此直接BFS也能过。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,mod=;
int c[N],sa[N],buf1[N],buf2[N],buf3[N],n,ka,nxt[N][];
char buf[N];
int s[N];
void Sort(int* x,int* y,int m) {
for(int i=; i<m; ++i)c[i]=;
for(int i=; i<n; ++i)++c[x[i]];
for(int i=; i<m; ++i)c[i]+=c[i-];
for(int i=n-; i>=; --i)sa[--c[x[y[i]]]]=y[i];
}
void da(int* s,int n,int m=) {
int *x=buf1,*y=buf2,*z=buf3;
x[n]=y[n]=-;
for(int i=; i<n; ++i)x[i]=s[i],y[i]=i;
Sort(x,y,m);
for(int k=,j=; k<n; k<<=,++j) {
int p=;
for(int i=; i<n; ++i)z[i]=x[nxt[i][j]],y[i]=i;
Sort(z,y,m);
for(int i=; i<n; ++i)y[i]=sa[i];
Sort(x,y,m),p=,y[sa[]]=;
for(int i=; i<n; ++i)y[sa[i]]=x[sa[i-]]==x[sa[i]]&&x[nxt[sa[i-]][j]]==x[nxt[sa[i]][j]]?p-:p++;
if(p==n)break;
swap(x,y),m=p;
}
}
int main() {
int T;
for(scanf("%d",&T); T--;) {
printf("Case #%d: ",++ka);
scanf("%d%s",&n,buf);
for(int i=; i<n; ++i)s[i]=buf[i];
for(int i=; i<n; ++i)nxt[i][]=((ll)i*i+)%n;
for(int k=; k<; ++k)
for(int i=; i<n; ++i)
nxt[i][k]=nxt[nxt[i][k-]][k-];
da(s,n);
for(int i=,u=sa[n-]; i<n; ++i,u=nxt[u][])printf("%c",s[u]);
puts("");
}
return ;
}