LuoguP3498 [POI2010]KOR-Beads

╰+哭是因爲堅強的太久メ 2021-11-26 07:38 114阅读 0赞

呀呀呀，临走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 }

转载于:https://www.cnblogs.com/zhenglw/p/11181790.html