menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[哈希]BZOJ2795(Poi2012)【A Horrible Poem】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

给出一个长度为 $n$ 的字符串和 $q$ 个询问,每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长度(最短循环节表示循环若干次之后和原串相同)。

解题报告

我怎么啥都不会啊,这道题好多知识点都不知道QAQ。

如何判断是否是周期?如果循环若干次是原串前缀,那么用KMP+border就可以得出,但是恰好怎么办?

其实也很easy啦,假设周期长度为 $len$ ,那么就是验证 $s_{[l_i,r_i-len]}=s_{[l_i+len,r_i]}$ 。怎么证明?画图yy一下……会发现只要第一段 $[l_i,l_i+x-1]$ 相同后面就会传递相同了。

很明显 $minlen|len$ ,那么我们可以直接枚举 $len$ 的因子,这样是 $O(\sqrt n)$ 的,先挖下素数可能可以过?

正确姿势:我们可以每次随便找个因子 $d$ ,如果 $n\over d$ 满足,那么就令 $n={n\over d}$ 。这样为什么是对的?由于 $a$ 满足 $b$ 满足就意味着 $gcd(a,b)$ 满足,所以不需要在意先枚举哪个因子,因为最终会枚举到最小的满足的因子。那么我们可以 $O(n)$ 预处理 $D(n)$ 表示 $n$ 最小的因子,然后就可以 $O(log_2n)$ 处理了。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef unsigned long long ULL;
const int maxn=500000;

int n,te;char s[maxn+5];ULL pw[maxn+5],ha[maxn+5];
int p[maxn+5],D[maxn+5];bool pri[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline int reads(char *s){
    int len=0;char ch=readc();while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();}
    while (islower(ch)) s[++len]=ch,ch=readc();return s[len+1]=0,len;
}
inline void Make(int n){
    pri[0]=pri[1]=true;
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,D[i]=i;
        for (int j=1,t=1;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;D[t]=p[j];if (!(i%p[j])) break;}
    }
}
inline bool check(int A,int B,int C,int D) {return ha[B]-ha[A-1]*pw[B-A+1]==ha[D]-ha[C-1]*pw[D-C+1];}
inline int Ask(int L,int R){
    int ans=R-L+1;
    for (int len=ans,MIN=D[len];len>1;MIN=D[len]){
        while (!(ans%MIN)&&check(L,R-ans/MIN,L+ans/MIN,R)) ans/=MIN;
        while (!(len%MIN)) len/=MIN;
    }
    return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(readi(n),reads(s),pw[0]=1);i<=n;i++)
        ha[i]=ha[i-1]*2333+s[i],pw[i]=pw[i-1]*2333;
    for (Make(n),readi(te);te;te--){
        int L,R;readi(L);readi(R);
        printf("%d\n",Ask(L,R));
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up