Beads

Beads

题目描述

Zxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块(子串)，每块有k(k>0)个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。

Zxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串(1，2，3)和 (3,2,1)是一样的。

写一个程序，为Zxl决定最适合的k从而获得最多不同的子串。

例如：

这一串珠子是： (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)

k=1的时候，我们得到3个不同的子串： (1),(2),(3)

k=2的时候，我们得到6个不同的子串： (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3的时候，我们得到5个不同的子串：

(1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2)

k=4的时候，我们得到5个不同的子串：

(1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)

输入

共有两行，第一行一个整数n代表珠子的长度，第二行是由空格分开的颜色ai（1<=ai<=n，n<=200005）。

输出

也有两行 第一行两个整数，第一个整数代表能获得的最大不同的子串个数，第二个整数代表能获得最大值的k的个数， 第二行输出所有的k（中间有空格）。

来源

[Poi2010]

---

好像没有hash的题解，放一篇

暴力枚举k+正反hash

hash的数不能是11，差评。。。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

#define maxn 200010

#define p 1000000007

using namespace std;

int n,s[maxn],h1[maxn],h2[maxn],c[maxn];

int ans,outp[maxn],tot,t1,t2,sum;

map<int,int>f;

void get(int l,int r)

{

    t1=h1[r]-h1[l-1]*c[r-l+1];

    t2=h2[l]-h2[r+1]*c[r-l+1];

    //cout<<t1<<' '<<t2<<' '<<l<<' '<<r<<endl;

    if(!f[t1]&&!f[t2]){

        f[t1]=f[t2]=1;

        sum++;

    }

}

int main(){

    cin>>n;

    c[0]=1;

    for(int i=1;i<=n;i++){

        scanf("%d",&s[i]);

        h1[i]=h1[i-1]*p+s[i];c[i]=c[i-1]*p;

        //cout<<h1[i]<<' '<<c[i]<<endl;

    }

    for(int i=n;i>=1;i--)h2[i]=h2[i+1]*p+s[i];

    for(int k=1;k<=n;k++){

        f.clear();sum=0;

        for(int i=1;i+k-1<=n;i+=k)get(i,i+k-1);

        if(sum>ans){

            ans=sum,tot=1,outp[1]=k;

        }

        else if(sum==ans)outp[++tot]=k;

    }

    printf("%d %d\n%d",ans,tot,outp[1]);

    for(int i=2;i<=tot;i++)printf(" %d",outp[i]);

    cout<<endl;

    return 0;

}