[POI2010]Beads

题目大意：
　　给定一个长度为$n(nleq200000)$的串$S_{1sim n}$，选择一个$l$，从$S_1$开始，将$S$分为连续的若干段，使得每一段长度为$l$。令$k$为分出来不同的子串个数（翻转后相同算作相同），求最大的$k$，以及有哪些$l$对应的答案为$k$。

思路：
　　枚举长度，求正反两个哈希去重。

#include<set>
#include<cstdio>
#include<cctype>
#include<vector>
typedef unsigned long long uint64;
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=200002,BASE=2333;
int a[N];
uint64 pow[N],h1[N],h2[N];
std::set<uint64> set;
std::vector<int> v;
inline uint64 hash1(const int &l,const int &r) {
    return h1[r]-h1[l-1]*pow[r-l+1];
}
inline uint64 hash2(const int &l,const int &r) {
    return h2[l]-h2[r+1]*pow[r-l+1];
}
int main() {
    const int n=getint();
    for(register int i=1;i<=n;i++) a[i]=getint();
    for(register int i=1;i<=n;i++) h1[i]=h1[i-1]*BASE+a[i];
    for(register int i=n;i>=0;i--) h2[i]=h2[i+1]*BASE+a[i];
    for(register int i=pow[0]=1;i<=n;i++) pow[i]=pow[i-1]*BASE;
    int ans=0;
    for(register int i=1;ans*i<=n;i++) {
        set.clear();
        int tmp=0;
        for(register int j=1;i+j-1<=n;j+=i) {
            const int h1=hash1(j,j+i-1),h2=hash2(j,j+i-1);
            if(!set.count(h1)||!set.count(h2)) {
                set.insert(h1),set.insert(h2);
                tmp++;
            }
        }
        if(tmp>ans) {
            ans=tmp;
            v.clear();
        }
        if(tmp==ans) v.push_back(i);
    }
    printf("%d %lu
",ans,v.size());
    for(register unsigned i=0;i<v.size();i++) {
        printf("%d%c",v[i]," 
"[i==v.size()-1]);
    }
    return 0;
}