2018南京站网络赛 I - Skr Manacher +hash拉链法

题目链接：https://nanti.jisuanke.com/t/A1955
题目大意：给出一个只含数字的字符串，求出字符串中所有本质不同的字符串所表示的十进制数的和

思路：哈希是回文自动机的裸题。用Manacher +hash可以A。Manacher找出所有的回文子串。用hash拉链法去个重。记录区间的十进制的哈希前缀和。直接求一个字串的贡献。这题hash不用自然溢出会WA。

#include <bits/stdc++.h>
using namespace std;
#define  LL long long
const int maxn=2000005;
const int Mod=1e9+7;
const int mod=2000007;
LL hs[4000005], Tep[4000005];
LL ans=0;
struct Hash_list{

    int head[4000005], nxt[4000005], cnt;
    LL v[4000005];//最多可能的哈希值的个数
    void init(){
        cnt=0;
        memset(head, -1, sizeof(head));
        memset(nxt, -1, sizeof(nxt));
    }
    bool _insert(unsigned LL now){//是否存在这个哈希值，如果不存在加入
        int u=now%mod;
        for(int i=head[u]; i!=-1; i=nxt[i]){
            if(v[i]==now) return 1;//如果存在
        }
        //加入这个值
        nxt[++cnt]=head[u];
        head[u]=cnt;
        v[cnt]=now;
        return 0;
    }
}hx_list;

struct Hash_char{
    unsigned LL base=1313131;
    unsigned LL p[4000005], g[4000005];
    void getp(){
        p[0]=1;
        for(int i=1; i<maxn; i++){
            p[i]=p[i-1]*base;
        }
    }
    LL Hash(char s[]){
        int len=strlen(s+1);
        g[0]=0, g[1]=s[1];
        for(int i=2; i<=len; i++){
            g[i]=(g[i-1]*base+s[i]);
        }
        return g[len];
    }
    LL getLR(int l, int r){
        LL ans=g[r]-g[l-1]*p[r-l+1];
        return ans;
    }
}hc;

struct Manacher{
    int p[4000005];
    int work(char *s){
        int len=strlen(s),id=0,maxlen=0;
        for(int i=len;i>=0;--i){
            s[i+i+2]=s[i]; s[i+i+1]='#';
        }
        s[0]='*';
        hx_list.init();
        for(int i=2;i<2*len+1;++i){
            if(p[id]+id>i)p[i]=min(p[2*id-i],p[id]+id-i);
            else p[i]=1;
            while(s[i-p[i]] == s[i+p[i]]){
                ++p[i];
                if (i%2==0 && p[i]&1){
                    int b = p[i]/2, l = i/2-b, r = i/2+b;
                    if (l==r) continue;
                    //cout<<l<<" "<<r<<endl;
                    if(!hx_list._insert(hc.getLR(l, r))){
                        ans+=((hs[r]-hs[l-1]*Tep[r-l+1]%Mod)+Mod)%Mod;
                    }
                }
                else if (i&1 && !(p[i]&1)){
                    int b = p[i]/2, l = i/2-b+1, r = i/2+b;
                    //cout<<l<<" "<<r<<endl;
                    if(!hx_list._insert(hc.getLR(l, r))){
                        ans+=((hs[r]-hs[l-1]*Tep[r-l+1]%Mod)+Mod)%Mod;
                    }
                }
                ans%=Mod;
            }
            if(id+p[id]<i+p[i])id=i;
            if(maxlen<p[i])maxlen=p[i];
        }
        return maxlen-1;
    }
}la;

char s[4000005*2], ST[4000005], vis[30];
int main(){
    scanf("%s",ST+1);
    int n=strlen(ST+1);
    Tep[0]=1;
    hc.getp();
    for(int i=1; i<=n; i++){
        s[i-1]=ST[i];
        hs[i]=(hs[i-1]*10+ST[i]-'0')%Mod;
        Tep[i]=(Tep[i-1]*10)%Mod;
        if(vis[ST[i]-'0']==0){
            //cout<<ST[i]-'0'<<endl;
            vis[ST[i]-'0']=1;
            ans+=ST[i]-'0';
        }
    }
    //cout<<ans<<endl;
    hc.Hash(ST);
    la.work(s);
    printf("%lld\n", ans);

    return 0;
}