HDU 6223 Infinite Fraction Path 后缀数组
每个节点都有唯一后继。所以,可以用倍增求后缀数组。
节点的前趋个数可能不唯一,所以我们可以用vector<int> pre[N][20]
来记录每个节点的前趋。
code
2964/3000 ms
命真大!
#include <iostream> #include <time.h> #include <vector> #include <cmath> using namespace std; const int N=150002; int T, n, cas; char s[N]; int sa[N], cc[N], t1[N], t2[N]; int nex[N][22]; vector<int> pre[N][22]; int LG[N]; void perlude() { for(int i=1;i<N;i++) LG[i] = (int)log2(i); } void rmqProcess() { int B = LG[n]; for(int i=0;i<n;i++) for(int j=0;j<=B;j++) nex[i][j]=-1, pre[i][j].clear(); for(int i=0;i<n;i++) { int j=(1LL*i*i+1)%n; nex[i][0] = j; pre[j][0].push_back(i); } for(int i=1;i<=B;i++) for(int j=0;j<n;j++) { nex[j][i]=nex[nex[j][i-1]][i-1]; pre[nex[nex[j][i-1]][i-1]][i].push_back(j); } } bool cmp(int *y, int a,int b,int k){ int a1=y[a]; int b1=y[b]; int a2=y[nex[a][k]]; int b2=y[nex[b][k]]; return (a1==b1)&&(a2==b2); } void build_sa(int m) { int *x=t1,*y=t2; for(int i=0;i<m;i++) cc[i]=0; for(int i=0;i<n;i++) ++ cc[x[i]=(s[i]-'0')]; for(int i=1;i<m;i++) cc[i]+=cc[i-1]; for(int i=n-1;i>=0;i--) sa[--cc[x[i]]]=i; int counter = 0; for(int k=1;k<=n;k<<=1,counter++) { int p=0; for(int i=0;i<n;i++) for(int j=0;j<pre[sa[i]][counter].size();j++) y[p++] = pre[sa[i]][counter][j]; for(int i=0;i<m;i++) cc[i]=0; for(int i=0;i<n;i++) ++cc[x[y[i]]]; for(int i=1;i<m;i++) cc[i]+=cc[i-1]; for(int i=n-1;i>=0;i--) sa[--cc[x[y[i]]]]=y[i]; std::swap(x,y); m=1, x[sa[0]]=0; for(int i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],counter) ? m-1 : m++; if (m>=n) break; } } void print(int x) { printf("Case #%d: ", ++cas); for(int i=0;i<n;i++) { printf("%c", s[x]); x=(1LL*x*x+1)%n; } printf("\n"); } int main() { perlude(); scanf("%d", &T); while(T --) { scanf("%d%s", &n,s); rmqProcess(); build_sa(10); print(sa[n-1]); } }