bzoj 2795 [Poi2012]A Horrible Poem hash+线性筛

题目大意

bzoj 2795

给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节。

如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到。

n<=500,000 , q<=2,000,000

分析

判循环节用hash

\(O(q\sqrt n)\)枚举因子?

TLE

注意一个特殊的性质

若长度len可为循环节,则若(klen) | n,(klen)也为循环节

不会出现两个循环节长度互质除非1是循环节

由于已知整个串是循环节

于是我们可以枚举质因子判断循环节能否缩短

线性筛预处理一波

\(O(q\log n)\)

原理

每个循环节都可以被最短循环节复制k倍表示

所以从原串缩短的过程中,能被最短循环节表示的本质没变,依然可以继续缩短

(反证假设不可以被最短循环节表示,则有它们的gcd才是最短循环节)

至于证明如果长度A是循环节,长度B是循环节,那么gcd(A,B)也是循环节

根据扩欧,存在 Ax+By=g

且根据循环节定义\(S[i]=S[i+k_1A+k_2B]\)

则对于\(\forall i\)都有\(S[i]=S[i+Ax+By]=S[i+gcd(A,B)]\)

solution

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int M=500007;
const ull W=131; inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
} int n,m;
char s[M];
ull hsh[M],pw[M];
int prime[M],cnt;
int vis[M];
int split[M][20]; void init(){
int i,j,k,t;
vis[1]=1;
for(i=2;i<M;i++){
if(!vis[i]){
prime[++cnt]=i;
split[i][0]=1;
split[i][1]=i;
}
for(j=1;j<=cnt;j++){
if((LL)i*prime[j]>=M) break;
t=i*prime[j];
vis[t]=1;
for(k=1;k<=split[i][0];k++) split[t][k]=split[i][k];
split[t][0]=split[i][0];
if(i%prime[j]==0) break;
split[t][++split[t][0]]=prime[j];
}
}
} ull gethsh(int x,int y){
int len=y-x+1;
return hsh[y]-hsh[x-1]*pw[len];
} int main(){
int i,j,x,y,len,z,tp,pri;
n=rd();
scanf("%s",s+1);
m=rd();
init();
for(hsh[0]=0,i=1;i<=n;i++) hsh[i]=hsh[i-1]*W+s[i];
for(pw[0]=1,i=1;i<=n;i++) pw[i]=pw[i-1]*W;
while(m--){
x=rd(),y=rd();
len=y-x+1;
z=len;
for(j=1;j<=split[z][0];j++){
pri=split[z][j];
while(len%pri==0){
tp=len/pri;
if(gethsh(x,y-tp)!=gethsh(x+tp,y)) break;
len/=pri;
}
}
printf("%d\n",len);
}
return 0;
}
上一篇:nodejs项目的model操作mongo


下一篇:如何解决自定义ToolBar起始位置的空格(左对齐)问题