本文共 1332 字，大约阅读时间需要 4 分钟。
给定字符串,求给定l,r区间的最短循环节长度.
显然区间长度循环节长度是区间长度m的因数，但是这样直接写个q根号m的暴力就肯定T掉啦。
想了挺久发现了一个喵喵的做法,不难发现，每个区间的某个字母必须在一个循环节里都出现,若这个字母出现k次，那么循环节的个数必须是k的因数，那么循环节个数就在这个区间gcd(k)范围内.
我们可以先预处理出前缀和数组保存每个区间每个字母出现次数，预处理除字符串hash值，然后枚举到根号gcd就够了.
这样复杂度是q根号gcd(k)，十分玄学的复杂度,于是我在洛谷和loj就T成了90分,可能代码写丑了吧，不过在bzoj上AC了。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define ll long long 9 #define out(a) printf("%d",a)10 #define writeln printf("\n")11 const int N=5e5+50;12 const int MOD=1e9+7;13 const int base=233;14 using namespace std;15 int n,q,l,r,ln;16 int num,numn,numns,len,ans=0;17 ll Hash[N],Pow[N];18 int cnt[27][N];19 char s[N];20 int read()21 {22 int s=0,t=1; char c;23 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();}24 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}25 return s*t;26 }27 ll readl()28 {29 ll s=0,t=1; char c;30 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();}31 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}32 return s*t;33 }34 ll get(int l,int r)35 {36 if (l<=r) return (Hash[r]-(ll)Hash[l-1]*Pow[r-l+1]%MOD+MOD)%MOD;37 return 0;38 }39 void hashs(char s[])40 {41 for (int i=0;i
转载于:https://www.cnblogs.com/Kaleidoscope233/p/9563058.html
