BZOJ 2081: [Poi2010]Beads

Description

问把n截成每个长度后不同子串个数.

Sol

调和极数＋Hash.

首先这是一个式子 \(n\sum_{i=1}^n \frac {1}{i}\) .

这东西就是调和极数再乘上 \(n\) ,他趋近于\(nlnn\)

正反哈希一下.

Code

/**************************************************************

    Problem: 2081

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:6420 ms

    Memory:58552 kb

****************************************************************/

#include <bits/stdc++.h>

using namespace std;

#define debug(a) cout<<#a<<"="<<a<<" "

typedef long long LL;

const int N = 2e5+50;

const LL bs = 666671;

const LL p = 5831801;

LL n,ans,ans1;

LL a[N],b[N],rb[N],v[2][N];

vector< int > as;

struct HashTable {

    int h[p],nxt[p],cnt;

    int q[N],t;

    LL v[N];

    void insert(LL x,LL val) {

        v[++cnt]=val,nxt[cnt]=h[x],h[x]=cnt;

        q[++t]=x;

    }

    LL find(LL x,LL val) {

        for(int i=h[x];i;i=nxt[i]) if(v[i]==val) return 1;

        return -1;

    }

    void clear() {

        for(int i=1;i<=t;i++) h[q[i]]=0;

        cnt=0,t=0;

    }

}hh;

inline LL in(LL x=0,char ch=getchar()) { while(ch>'9' || ch<'0') ch=getchar();

    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }

inline LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }

LL GetVal(int kd,LL l,LL r) {

    if(!kd) return (v[kd][r]-v[kd][l-1]+p)%p*rb[l-1]%p;

    else return (v[kd][l]-v[kd][r+1]+p)%p*rb[n-r]%p;

}

int main() {

    n=in();

    for(int i=1;i<=n;i++) a[i]=in();

    b[0]=b[1]=1;for(int i=2;i<=n;i++) b[i]=b[i-1]*bs%p;

    rb[0]=1,rb[1]=Pow(bs,p-2);for(int i=2;i<=n;i++) rb[i]=rb[i-1]*rb[1]%p;

    for(int i=1;i<=n;i++) v[0][i]=(v[0][i-1]+a[i]*b[i]%p)%p;

    for(int i=n;i>=1;i--) v[1][i]=(v[1][i+1]+a[i]*b[n-i+1]%p)%p;

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

        int r=0;

        hh.clear();

//      cout<<i<<":"<<endl;

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

            LL vv1=GetVal(0,j,j+i-1),vv2=GetVal(1,j,j+i-1);

//          debug(vv1),debug(vv2)<<endl;

            if(vv1>vv2) swap(vv1,vv2);

            if(hh.find(vv1,vv2)==-1) hh.insert(vv1,vv2),r++;

        }

//      debug(r)<<endl;

//      cout<<"---------------------"<<endl;

        if(r>ans) as.clear(),as.push_back(i),ans=r;

        else if(r==ans) as.push_back(i);

    }

    ans1=as.size();

    printf("%lld %lld\n",ans,ans1);

    for(int i=0;i<ans1;i++) printf("%d%c",as[i]," \n"[i==ans1-1]);

    return 0;

}

/*

21

1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

*/