bzoj 2795 [Poi2012]A Horrible Poem hash+线性筛
2024-08-29 00:01:16
题目大意
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;
}
最新文章
- MySQL/MariaDB/PerconaDB-提权条件竞争漏洞
- Python_Day7_面向对象学习
- java筛选法求素数
- python if __name__ == &#39;__main__&#39;解析
- 【转帖】自助式BI的崛起:三张图看清商业智能和大数据分析市场趋势
- 学习C语言常用的几个网站
- MyBatis关联查询分页
- 2016年11月10日 星期四 --出埃及记 Exodus 20:1
- Inno Setup 插件大全
- ImportError: No module named &#39;commands&#39;
- 李洪强漫谈iOS开发[C语言-043]-练习
- Vivado HLS与System Generator:联系与区别
- 我30天在Stack Overflow问答网站上回答问题的感受
- 201521123022 《Java程序设计》 第一周学习总结
- npm缺少css-loader,/style-compiler,stylus-loader问题,npm没有权限无法全局更新问题【已解决】
- python列表的学习笔记
- C#连接字符串
- 解决ubuntu输入正确用户密码重新跳到无法登录
- H5外包团队 android视频压缩,使用ffmpeg方案
- JavaScript中判断整字类型最简洁的实现方法
热门文章
- 用户输入和while循环
- java基础—泛型
- Dapper学习总结
- 什么是静态代码块?java中如何使用空参构造方法自动生成不同名字的对象,使用非静态的属性和静态属性有什么区别,原因是什么?如何理解static关键字
- C++ 学习笔记(四)类的内存分配及this指针
- Optimization &; Map
- java的一些相关介绍(2013-10-07-163 写的日志迁移
- day 35 补充
- Huawei warns against &#39;Berlin Wall&#39; in digital world
- 用Python抓取并分析了1982场英雄联盟数据,教你开局前预测游戏对局胜负!