题意：给你一个字符串s，找到满足条件(s[i]的下一个字符是s[(i*i+1)%n])的最大字典序的长度为n的串。
思路：类似后缀数组，每次倍增来对以i开头的字符串排序，复杂度O(nlogn)。代码很多地方借鉴后缀数组。
倍增：比如这次排序好了长度为m的串，那么想扩展为长度为2*m的串则需要用i的排名为第一关键字，i+m的排名为第二关键字进行排序，这种排序正好可以使用基数排序。
下面是代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=;
int n;
int m;
int tp[maxn],Rank[maxn],SA[maxn],tax[maxn];
void Rsort()///SA为排名为i的元素所在的位置，tp为第二关键字，Rank作为第一关键字，Rank为i元素的排名。
{
for(int i=; i<=m; i++)tax[i]=;
for(int i=; i<=n; i++)tax[Rank[tp[i]]]++;
for(int i=; i<=m; i++)tax[i]+=tax[i-];
for(int i=n; i>=; i--)SA[tax[Rank[tp[i]]]--]=tp[i];
}
char st[maxn];
int go[maxn][];
int main()
{
int t;
while(~scanf("%d",&t))
{
int c=;
while(t--)
{
scanf("%d",&n);
scanf("%s",st+);
for(long long i=; i<=n; i++)
go[i][]=((i-)*(i-)+)%n+;///滚动数组，倍增查找i后面的第2^k的位置。
m=;
for(int i=; i<=n; i++)
tp[i]=i,Rank[i]=st[i]-'';
int p;
for(int t=; t<&&(<<t)<=n; t++)
{
for(int i=;i<=m;i++)tax[i]=;
for(int i=; i<=n; i++)tax[Rank[go[i][t&]]]++;
for(int i=;i<=m;i++)tax[i]+=tax[i-];
for(int i=;i<=n;i++)tp[tax[Rank[go[i][t&]]]--]=i;
Rsort();
swap(tp,Rank);
Rank[SA[]]=p=;
for(int i=; i<=n; i++)Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-]]&&tp[go[SA[i]][t&]]==tp[go[SA[i-]][t&]])?p:++p;
if(Rank[SA[n]]!=Rank[SA[n-]])break;///剪枝，如果已经能确定最大的了 直接break
m=p;
for(int i=;i<=n;i++)
go[i][!(t&)]=go[go[i][t&]][t&];///这里是倍增,go[i]代表i后面第2^t的元素的位置
}
printf("Case #%d: ",c++);
long long loc=SA[n]-;
for(int i=; i<n; i++,loc=(loc*loc+)%n)
printf("%c",st[loc+]);
puts("");
}
}
return ;
}