呀呀呀，临走10分钟刷一道水题

然而只是记一下第一次hash被卡

各种模数都被卡了...

本来想打双哈希了，后来皮了一下，模数改成了998244353，然后竟然A掉了

 

正着hash一遍，反着hash一遍

对于一个串都取正反hash值的min值，若其相同，则必然是相同串（不被卡的话）

计数用set就好了

 1 #include<bits/stdc++.h>
 2 #define ull unsigned long long
 3 using namespace std;
 4 inline int read(){
 5     int ans=0,f=1;char chr=getchar();
 6     while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
 7     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 8     return ans*f;
 9 }const int M=2e5+5,B=998244353;
10 ull f[M],ff[M],h[M];
11 int s[M],n,maxn,cnt,k[M];
12 inline void Hash(){int i;
13     for(i=1,h[0]=1;i<=n;i++) h[i]=h[i-1]*B,f[i]=f[i-1]*B+s[i];
14     for(i=n;i>=1;i--) ff[i]=ff[i+1]*B+s[i];
15 }
16 inline ull Get1(int l,int r){return f[r]-f[l-1]*h[r-l+1];}
17 inline ull Get2(int l,int r){return ff[l]-ff[r+1]*h[r-l+1];}
18 set<ull> ss;
19 inline int Calc(int k){
20     int t=0;ss.clear();
21     for(int i=1;i+k-1<=n;i+=k){
22         ull tmp=min(Get1(i,i+k-1),Get2(i,i+k-1));
23         ss.insert(tmp);
24     }return ss.size();
25 }
26 int main(){
27     n=read();
28     for(int i=1;i<=n;i++) s[i]=read();
29     Hash();
30     for(int i=1;i<=n;i++){
31         int now=Calc(i);
32         if(now>maxn) maxn=now,cnt=0;
33         if(now==maxn)k[++cnt]=i;
34     }
35     cout<<maxn<<" "<<cnt<<endl;
36     for(int i=1;i<=cnt;i++)    cout<<k[i]<<" ";
37     return 0;
38 }