2018南京网络赛 Skr（manacher奇偶模板+hash模板）

妖狐艹你老母 2022-05-14 04:24 152阅读 0赞

[传送门][Link 1]

题意：给一个只有‘1’~‘9’的串，求不同回文串代表数值的和

思路：马拉车找回文串，hash标记不同，hash方法求数值

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e6+10;
    const int mo=1e9+7;
    typedef long long ll;
    typedef unsigned long long ull;
    ull p=1000007, val[N<<1], bas[N], _hash[N];
    ll bas10[N], num[N], ans;
    int r[N], las[N], nxt[N], cnt;
    char s[N];
    
    bool HASH(ull h){
        int to=h%2000000;
        for(int i=las[to]; i; i=nxt[i])
            if(val[i]==h) return true;
        nxt[++cnt]=las[to];
        las[to]=cnt;
        val[cnt]=h;
        return false;
    }
    
    void _insert(int L, int R){
        ull h=_hash[R]-_hash[L-1]*bas[R-L+1];
        if(!HASH(h)){
            ll tmp=((num[R]-num[L-1]*bas10[R-L+1]%mo)%mo+mo)%mo;
            ans+=tmp;
            ans%=mo;
        }
    }
    
    void manacher(){
        scanf("%s", s+1);
        int len=strlen(s+1);
        bas10[0]=bas[0]=1;
        num[0]=_hash[0]=0;
        for(int i=1; i<=len; i++){
            bas[i]=bas[i-1]*p;
            _hash[i]=_hash[i-1]*p+s[i];
            bas10[i]=bas10[i-1]*10;
            bas10[i]%=mo;
            num[i]=num[i-1]*10+s[i]-'0';
            num[i]%=mo;
        }
    
        int mid=1, mx=0;
        cnt=0;
    
        s[0]='$'; s[++len]='&';
        for(int i=1; i<len; i++){
            _insert(i,i);
            r[i]=i<mx?min(r[2*mid-i], mx-i):1;
            while(s[i-r[i]]==s[i+r[i]]){
                _insert(i-r[i], i+r[i]);
                r[i]++;
            }
            r[i]--;
            if(i+r[i]>mx){
                mx=i+r[i];
                mid=i;
            }
        }
    
        memset(r, 0, sizeof r);
        memset(las, 0, sizeof las);
        cnt=0;
        mid=1, mx=0;
    
        for(int i=2; i<len; i++){
            if(i<mx) r[i]=min(r[2*mid-i], mx-i+1);
            while(i+r[i]<len&&s[i-r[i]-1]==s[i+r[i]]){
                _insert(i-r[i]-1, i+r[i]);
                r[i]++;
            }
            r[i]--;
            if(i+r[i]>mx){
                mx=i+r[i];
                mid=i;
            }
            if(r[i]<0) r[i]=0;//如果是负数，会使后面用到这个r的位置错位，导致超时
        }
        printf("%lld\n", ans);
    }
    
    int main(){
        manacher();
        return 0;
    }

[Link 1]: https://nanti.jisuanke.com/t/30998