hash+hash表+调和级数
关于调和级数（from baidu百科）：
在做题之前，我们需要先算算复杂度
我们至少要枚举子串的长度，并取出每个子串。
计算枚举的总复杂度
O(n+n/2+n/3+n/4+...+n/n)（分数向下取整）== O(n*(1+1/2+1/3+1/4+...+1/n))（分数向下取整）<= O(n*(1+1/2+1/3+1/4+...+1/n))
其中这个 1+1/2+1/3+1/4+...+1/n 通过一种叫调和级数的神奇方法可以得出
1+1/2+1/3+1/4+...+1/n ≈ ln n < log n
∴枚举的总复杂度 <= O( n log n )
所以如果比较和记录的复杂度可以达到 O(1)，我们就可以轻松愉快地（大雾）过掉了。
于是我们想到用hash瞎搞
我们预处理出主串的hash值，由于子串可以翻转，所以正序逆序都要算
然后取出子串的hash值（方法见代码），扔到hash表里判重
至于怎么搞hash表，用邻接表实现就好了。
但是我们每次枚举都要先清空hash表，时间占用太大了。
于是我们可以引入一个tim数组，存下时间戳，表示枚举长度 i 时这个子串被扔进去
当 tim 不同时，说明这是上次枚举的数据，已经失效，可以直接覆盖
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int read(){ char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+c-48,c=getchar(); return x; } typedef unsigned long long ull; #define N 200005 const ull bs=1e9+7; const ull Ph=13357771; int n,ans,pos[N],tp; int cnt,hd[Ph],nx[N*2],ti[N*2]; ull a[N],fac[N],h1[N],h2[N],v[N*2]; void ins(ull x,int nw){ nx[++cnt]=hd[x%Ph]; hd[x%Ph]=cnt; ti[cnt]=nw; v[cnt]=x; } int ask(ull x,int nw){ for(int i=hd[x%Ph];ti[i]==nw;i=nx[i]) if(v[i]==x) return 0; return 1; } int main(){ n=read(); fac[0]=1; for(int i=1;i<=n;++i){ a[i]=read(); fac[i]=fac[i-1]*bs; h1[i]=h1[i-1]*bs+a[i]; } for(int i=n;i>=1;--i) h2[i]=h2[i+1]*bs+a[i]; for(int k=1;k<=n;++k){ if(n/k<ans) break; int tt=0; cnt=0; for(int i=1;i+k-1<=n;i+=k){ ull p1=h1[i+k-1]-h1[i-1]*fac[k]; ull p2=h2[i]-h2[i+k]*fac[k]; if(ask(p1,k)&&ask(p2,k)) ins(p1,k),ins(p2,k),++tt; } if(tt>ans) ans=tt,pos[tp=1]=k; else if(tt==ans) pos[++tp]=k; }sort(pos+1,pos+tp+1); printf("%d %d ",ans,tp); for(int i=1;i<=tp;++i) printf("%d ",pos[i]); return 0; }