题目大意：有n个点， 每个点有一个数字0 - 9， 第 i 个点只能到 第(i * i + 1)个点，问你在哪个点出发走n次构成的数字串最大。
思路：利用求后缀数组的倍增比较思想， 许多细节需要注意。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int>>
using namespace std; const int N=2e5+;
const int M=1e4+;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9 + ; int n, tot, a[N], nx[N][], sa[N], t[N], t2[N], c[N], nxk[N], ans[N];
vector<int> prek[N];
void buildSa(int n, int m) {
int i, j, *x = t, *y = t2;
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[i] = a[i]]++, nxk[i] = i;
for(i = ; i < m; i++) c[i] += c[i - ];
for(i = n - ; i >= ; i--) sa[--c[x[i]]] = i; for(int k = ; k <= n; k <<= ) {
for(i = ; i < n; i++) nxk[i] = nx[nxk[i]][], prek[i].clear();
for(i = ; i < n; i++) prek[nxk[i]].push_back(i);
int p = ;
for(i = ; i < n; i++) {
for(j = ; j < prek[sa[i]].size(); j++)
y[p++] = prek[sa[i]][j];
}
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[y[i]]]++;
for(i = ; i < m; i++) c[i] += c[i - ];
for(i = n - ; i >= ; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = ; x[sa[]] = ;
for(i = ; i < n; i++) {
if(y[sa[i - ]] == y[sa[i]] && y[nxk[sa[i - ]]] == y[nxk[sa[i]]])
x[sa[i]] = p - ;
else x[sa[i]] = p++;
}
if(p >= n) break;
m = p;
}
}
int main() {
int T; scanf("%d", &T);
for(int cas = ; cas <= T; cas++) {
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%1d", &a[i]);
} for(int i = ; i < n; i++) {
nx[i][] = (1ll * i * i + ) % n;
} for(int j = ; j < ; j++) {
for(int i = ; i < n; i++) {
nx[i][j] = nx[nx[i][j - ]][j - ];
}
}
buildSa(n, );
tot = ;
int now = sa[n - ];
for(int i = ; i <= n; i++) {
ans[tot++] = a[now];
now = nx[now][];
}
printf("Case #%d: ", cas);
for(int i = ; i < tot; i++)
printf("%d", ans[i]);
puts("");
}
return ;
}
/*
*/