HDU - 6223（倍增、哈希）
90nwyn
2020-12-04 12:47:20
[题目链接](https://vjudge.net/problem/HDU-6223)
------------
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M=2e5+5;
const ull base=131;
int n,nxt[M][20];
ull haxi[M][20],p[M];
char s[M];
void init()
{
for(int j=0;j<n;j++)nxt[j][0]=((ll)j*j+1)%n,haxi[j][0]=s[j]-'a';
for(int i=1;i<20;i++)
for(int j=0;j<n;j++)
nxt[j][i]=nxt[nxt[j][i-1]][i-1],haxi[j][i]=haxi[j][i-1]*p[i-1]+haxi[nxt[j][i-1]][i-1];
}
int check(int a,int b,int t)
{
if(!t)return s[a]>s[b];
if(haxi[a][t-1]!=haxi[b][t-1])return check(a,b,t-1);
return check(nxt[a][t-1],nxt[b][t-1],t-1);
}
void output(int pos)
{
for(int i=1;i<=n;i++)
{
printf("%c",s[pos]);
pos=((ll)pos*pos+1)%n;
}
puts("");
}
int main()
{
p[0]=base;
for(int i = 1; i <20; i ++)p[i] =p[i-1] * p[i-1];
int T,cas=0;scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s);
init();
int ans=0;
for(int i=1;i<n;i++)
if(check(i,ans,18))ans=i;
printf("Case #%d: ",++cas);
output(ans);
}
return 0;
}
```