[FZU/FOJ][1872][A New Sequence Problem][后缀数组]

问题最终转化为，求出 height 数组后，求 max{ (j- i+ 1)* ( min( height[i..j] ) ) }，相当于找一个最大的矩形。

求F(a^b)% c  因为 c 比较小，可求出其循环节。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef __int64 LL;

int const N= 200110;
int wa[N], wb[N], ws[N], wv[N];
int rank[N], height[N], sa[N], r[N], n;
int a, b, c;
int fib[1000010], hash[1010][1010];
int L[N], R[N];

int cmp( int* r, int a, int b, int L ){
	return r[a]== r[b] && r[a+ L]== r[b+ L];
}

void da( int* r, int* sa, int n, int m ){
	int i, j, p, *x= wa, *y= wb, *t;
	for( i= 0; i< m; ++i ) ws[i]= 0;
	for( i= 0; i< n; ++i ) ws[ x[i]= r[i] ]++;
	for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
	for( i= n- 1; i>= 0; i-- ) sa[ --ws[ x[i] ] ]= i;
	
	for( j= 1, p= 1; p< n; j*= 2, m= p ){
		for( p= 0, i= n- j; i< n; ++i ) y[p++]= i;
		for( i= 0; i< n; ++i )
		if( sa[i]>= j ) y[p++]= sa[i]- j;
		
		for( i= 0; i< n; ++i ) wv[i]= x[ y[i] ];
		for( i= 0; i< m; ++i ) ws[i]= 0;
		for( i= 0; i< n; ++i ) ws[ wv[i] ]++;
		for( i= 1; i< m; ++i ) ws[i]+= ws[i-1];
		for( i= n- 1; i>= 0; i-- ) sa[ --ws[ wv[i] ] ]= y[i];
		
		t= x, x= y, y= t; p= 1; x[ sa[0] ]= 0;
		for( i= 1; i< n; ++i )
		x[ sa[i] ]= cmp( y, sa[i-1], sa[i], j )? p- 1: p++;
	}
}

void calheight( int* r, int* sa, int n ){
	int i, j, k= 0;
	for( i= 1; i<= n; ++i ) rank[ sa[i] ]= i;
	
	for( i= 0; i< n; height[ rank[i++] ]= k )
	for( k? k--: 0, j= sa[ rank[i]- 1]; r[i+ k]== r[j+ k]; k++ );
}

int getRepeat(){
	for( int i= 0; i<= c; ++i )
	for( int j= 0; j<= c; ++j ) hash[i][j]= 0;
	
	fib[0]= 0; fib[1]= 1; hash[0][1]= 1;
	
	int i= 2;
	while( true ){
		fib[i]= ( fib[i-1]+ fib[i-2] )% c;
		if( hash[ fib[i-1] ][ fib[i] ] ) return i;
		hash[ fib[i-1] ][ fib[i] ]= 1;
		i++;
	}
}

int modExp( int a, int b, int c ){
	LL t= 1, x= a% c;
	while( b ){
		if( b& 1 ) t= t* x% c;
		x= x* x% c; b>>= 1;
	}
	return t% c;
}

int main(){
	int test;

	scanf("%d",&test );
	for( int te= 1; te<= test; ++te ){
		scanf("%d%d%d%d", &a, &b, &c, &n );
		int mod= getRepeat()- 1;
		
		int ans= modExp( a, b, mod );
		
		r[0]= ( ( (LL)fib[ans]* (LL)c )% 200003 );
		for( int i= 1; i< n; ++i )
		r[i]= ( ( (LL)r[i-1]* (LL) r[i-1] )% 200003 );
		
		r[n]= 0;
		for( int i= 0; i< n; ++i ) r[i]++;
		
		da( r, sa, n+ 1, 200010 );
		calheight( r, sa, n );
		
		int i, j;
		for( i= 0; i<= n; ++i ) L[i]= 0, R[i]= 0;
		for( i= 1; i<= n; ++i ){
			for( j= i; j> 1 && height[j]<= height[j-1]; j= L[j-1] );
			L[i]= j;
		}
		
		LL res= 0;
		for( i= n; i>= 1; i-- ){
			for( j= i; j< n && height[j]<= height[j+1]; j= R[j+1] );
			R[i]= j;
			
			if( (LL)( R[i]- L[i]+ 1 )* height[i]> res )
			res= (LL)( R[i]- L[i]+ 1 )* height[i];
		}
		printf("Case %d: %I64d\n", te, res );
	}
	
	return 0;
}