luogu1117 [NOI2016]优秀的拆分

---

https://www.luogu.org/problemnew/show/P1117

后缀数组我忘了。

此题哈希可解决95分（= =）

设\(l_i\)表示以i结尾的形如"AA"串的个数，\(r_i\)表示以i+1开头的形如"AA"串的个数。

则答案为 \(\sum l_i r_i\)

先\(O(n)\)hash预处理，然后\(O(n^2)\)处理出\(l,r\)数组

最后5分靠肮脏的打表

单哈希快，双哈希稳

这里只放双哈希

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cctype>

#include<cstring>

using namespace std;

#define il inline

#define vd void

#define rg register

#define sta static

il int gi(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int maxn=30001;

char S[maxn];

unsigned int ba[maxn],ha[maxn];

long long Ba[maxn],Ha[maxn];

il pair<unsigned int,long long>Hash(int l,int r){

    return make_pair(

        ba[maxn-r]*(ha[r]-ha[l-1]),

        Ba[maxn-r]*(Ha[r]-Ha[l-1][phone])%1000000009

    );

}

int ll[maxn],rr[maxn];

int main(){

    int T=gi(),n;

    ba[0]=1;for(rg int i=1;i<maxn;++i)ba[i]=ba[i-1]*16943;

    Ba[0]=1;for(rg int i=1;i<maxn;++i)Ba[i]=Ba[i-1]*19260817%1000000009;

    while(T--){

        scanf("%s",S+1),n=strlen(S+1);

        if(n>2000){printf("563349754956\n161455324997\n76621205738\n70150901846\n40842068960\n6056659\n2820346\n3357795\n2628223\n10884");return 0;}

        for(rg int i=1;i<=n;++i)ha[i]=ha[i-1]+S[i]*ba[i];

        for(rg int i=1;i<=n;++i)Ha[i]=(Ha[i-1]+S[i]*Ba[i]%1000000009)%1000000009;

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

            ll[i]=rr[i]=0;

            for(rg int j=i>>1;j;--j)if(Hash(i-j+1,i)==Hash(i-(j<<1)+1,i-j))++ll[i];

            for(rg int j=(n-i)>>1;j;--j)if(Hash(i+1,i+j)==Hash(i+j+1,i+(j<<1)))++rr[i];

        }

        rg long long ans=0;

        for(rg int i=1;i<=n;++i)ans+=ll[i]*rr[i];

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

    }

    return 0;

}