问题最终转化为,求出 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;
}
分享到:
相关推荐
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
输入数组第一行为一个数X,表示有X组输入数据。每组数据只有一行,包括4个数T(1 ), K(0 ), U(1 ), V(1 )。 Output 对于每组数据,输出只有一个整数,如果兔子获胜,则输出0,如果乌龟获胜则输出1,如果同时到达,...
2021FZU计算机视觉作业(八)
2021FZU计算机视觉期末复习
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
fzu大数据基础实验4
(This is a collection of documents relating to our Leapfrog Handbook project, including member grouping information forms, task summary documents for each group member, a project diary, and other ...
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
FZU2021计算机视觉答案(三)
FZU2021计算机视觉答案(四)
2021FZU计算机视觉答案(五)
2021FZU计算机视觉答案(二 )
2021FZU计算机视觉答案(六)
2011 ACM 多校联合 2011 MU11 13 FZU