题意：

给出一个全是数字的字符串S，求其中所有回文串的总和（长得一样的算一个）。S的长度小于等于2000000。

思路：

法一：马拉车+哈希

字符串的各种算法是去年学的现在都忘光了…

所以先复习了一下马拉车（以前好像没有搞得很明白）。

参考博客：https://www.jianshu.com/p/799bc53d4e3d

这篇写得很好。

理解马拉车的原理以后可以知道扩展之前就已经把当前已知的部分回文利用起来了，所以这里已经去掉了一些重复的，但是还是有一些其他重复的。

在扩展的过程中取出新产生的子串，算出哈希值看有没有出现过，如果没有出现过就算在答案里，出现过就不算。

所以这里要预处理出哈希值，前缀和和一些次方的值。

哈希表这里我看到群里说可以用gp_hash_table…然而我用了却MLE了…我觉得可能是这个ull太大了，所以我把它取模变成int存起来就WA了…考虑到2000000的子串数量，的确是会发生冲突。

所以就只能参考网上手写了个拉链法的哈希表。

感觉做一道题好像学了挺多东西的啊hhh。

法二：回文树

留坑。

代码：

法一：

typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
const ull base=131;
const int mod=4000007;
char a[2001000];//aba
char anew[4001000];//$#a#b#a#
int p[4001000];//新串中以第i个字符为对称轴的回文串的回文半径
//p[i]-1为原串中以i为对称轴的最长回文串的长度
ull hsh[4001000],bas[4001000];//哈希值
ll pre[4001000],tbas[4001000];//前缀和
int head[4001000],nxt[4001000],cnt=0;
ull val[4001000];
void init()
{
    int len=strlen(a);
    anew[0]='$';
    anew[1]='#';
    int num=2;
    for(int i=0; i<len; i++)
    {
        anew[num++]=a[i];
        anew[num++]='#';
    }
    anew[num]='\0';
    //puts(anew);
}
bool used(ull x)//手写拉链法哈希
{
    int temp=x%mod;
    for(int i=head[temp];i!=-1;i=nxt[i])
        if(val[i]==x)return true;
    val[++cnt]=x;
    nxt[cnt]=head[temp];
    head[temp]=cnt;
    return false;
}
ll solve(int l,int r)
{
    ull temp=hsh[r]-hsh[l-1]*bas[r-l+1];
    if(used(temp))return 0;
    ll sum=0;
    sum=(pre[r]-(pre[l-1]*tbas[(r-l)/2+1])%MOD+MOD)%MOD;
    //printf("sum=%lld\n",sum);
    return sum;
}
ll Manacher()
{
    init();
    cnt=0;
    memset(head,-1,sizeof(head));
    int len=strlen(anew);
    //printf("%d\n",len);
    int id;//mx对应的回文串的对称轴所在的位置
    int mx=0;//当前访问到的所有回文子串，所能触及的最右一个字符的位置
    hsh[0]=0;pre[0]=0;
    bas[0]=1;tbas[0]=1;
    for(int i=1;i<len;i++)
    {
        hsh[i]=hsh[i-1]*base+anew[i];
        bas[i]=base*bas[i-1];
        tbas[i]=(10*tbas[i-1])%MOD;
        if(anew[i]>='0'&&anew[i]<='9')
            pre[i]=(pre[i-1]*10+anew[i]-'0')%MOD;
        else pre[i]=pre[i-1];
    }
    /*for(int i=1;i<len;i++)
     printf("%c ",anew[i]);
     printf("\n");
     for(int i=1;i<len;i++)
     printf("%lld ",pre[i]);
     printf("\n");*/
    ll ans=0;
    for(int i=1; i<len; i++)
    {
        if(anew[i]!='#')
        {
            //printf("[%d,%d]\n",i,i);
            ans=(ans+solve(i,i))%MOD;
        }
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);//这些已经算过了就不用再算
        else
            p[i]=1;
        while(anew[i-p[i]]==anew[i+p[i]])//扩展
        {
            if(anew[i-p[i]]!='#')
            {
                //printf("[%d,%d]\n",i-p[i],i+p[i]);
                ans=(ans+solve(i-p[i],i+p[i]))%MOD;//扩展的时候要算
            }
            p[i]++;
        }
        if(mx<i+p[i])//最右的字符的位置要改变
        {
            id=i;
            mx=i+p[i];
        }
    }
    return ans;
}
int main()
{
    scanf("%s",a);
    printf("%lld\n",Manacher());
    return 0;
}

法二：

留坑。