BZOJ2795: [Poi2012]A Horrible Poem

2019-11-06 06:44:11

字體：大中小

供稿：網(wǎng)友

一個(gè)字符串若被分成k個(gè)循環(huán)節(jié)，每個(gè)循環(huán)節(jié)里每種字母出現(xiàn)次數(shù)肯定都是一樣的，那么循環(huán)節(jié)的個(gè)數(shù)k一定是這段字符串里每種字母出現(xiàn)次數(shù)的gcd的約數(shù)，然后枚舉k，hash判一下

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void down(int &x,int y){if(x>y)x=y;}const int maxn = 510000;int gcd(int a,int b){return a==0?b:gcd(b%a,a);}ll hk=233,hk2=1e9+7;char s[maxn];ll sum[maxn],pw[maxn];int num[maxn][26];int n,q;bool judge(int l1,int r1,int l2,int r2){ ll s1=sum[r1]-sum[l1-1]*pw[r1-l1+1]; ll s2=sum[r2]-sum[l2-1]*pw[r1-l1+1]; return s1==s2;}int main(){ read(n); scanf("%s",s+1); for(int i=1;i<=n;i++) { for(int j=0;j<26;j++) num[i][j]=num[i-1][j]+(s[i]-j=='a'); } for(int i=1;i<=n;i++) sum[i]=sum[i-1]*hk+(ll)s[i]; pw[0]=1ll; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*hk; read(q); while(q--) { int l,r; read(l); read(r); int lr=(r-l+1); int D=lr; for(int i=0;i<26;i++) D=gcd(D,num[r][i]-num[l-1][i]); int ans=lr; int k=sqrt(D); for(int i=1;i<=k;i++) if(D%i==0) { int tk; tk=lr/i; if(judge(l,r-tk,l+tk,r)) down(ans,tk); if(i*i==D) break; tk=lr/(D/i); if(judge(l,r-tk,l+tk,r)) down(ans,tk); }