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]);
    }
}