BZOJ2081: [Poi2010]Beads

Description

给定一个长度为n的数字串,求所有的k满足当将这个数字串从左到右分成大小为k的块时不同的块数量最多(反转同构算同一种). 

Input

共有两行,第一行一个整数n(n≤200000)代表珠子的长度,第二行是由空格分开的颜色ai(1≤ai≤n). 

Output

两行,第一行两个整数,第一个整数代表能获得的最大不同的子串个数，第二个整数代表能获得最大值的k的个数，第二行输出所有
的k(中间有空格). 

Sample Input

21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

Sample Output

6 1
2

Solution

可以直接暴力枚举k,听大佬说有个叫调和级数的东西,反正时间就是不会爆,然后就是裸的Hash了,因为反转同构算同一种,所以正反都来一遍哈希,截取的时候直接相乘,为了防冲就突取了两个模,弱弱地打了四个Hash数组…

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
const int N=200005,base=23333,mod1=10000007,mod2=10000009;
using namespace std;
ll a[N],num[N],pow1[N],pow2[N],hash1[N],hash2[N],hash3[N],hash4[N];
ll anss,ans,cnt,n,tot;
struct data{
    ll x,y;
}f[N];
bool cmp(data x,data y){
    if (x.x!=y.x)   return x.x<y.x;
    return x.y<y.y;
}
void pre(){
    pow1[0]=pow2[0]=1;
    for(int i=1;i<=n;i++){
        pow1[i]=pow1[i-1]*base%mod1;
        pow2[i]=pow2[i-1]*base%mod2;
    }
    for (int i=1;i<=n;i++){
        hash1[i]=(hash1[i-1]*base+a[i])%mod1;
        hash2[i]=(hash2[i-1]*base+a[i])%mod2;
    }
    for (int i=n;i;i--){
        hash3[i]=(hash3[i+1]*base+a[i])%mod1;
        hash4[i]=(hash4[i+1]*base+a[i])%mod2; 
    }
}
int main(){
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",a+i);
    pre();
    for(int k=1;k<=n;k++){
        tot=n/k,ans=0;
        for(int i=1;i<=tot;i++){
            f[i].x=((hash1[i*k]-hash1[(i-1)*k]*pow1[k]%mod1+mod1)%mod1)*(hash3[(i-1)*k+1]-hash3[i*k+1]*pow1[k]%mod1+mod1)%mod1;
            f[i].y=((hash2[i*k]-hash2[(i-1)*k]*pow2[k]%mod2+mod2)%mod2)*(hash4[(i-1)*k+1]-hash4[i*k+1]*pow2[k]%mod2+mod2)%mod2;
        }
        sort(f+1,f+tot+1,cmp);
        for(int i=1;i<=tot;i++) ans+=f[i].x!=f[i-1].x||f[i].y!=f[i-1].y;
        if (ans>anss){
            cnt=1; anss=ans; num[1]=k;
        }else   if (ans==anss)  num[++cnt]=k;
    }
    printf("%lld %lld\n",anss,cnt);
    for (int i=1;i<cnt;i++) printf("%lld ",num[i]);
    printf("%lld",num[cnt]);
}