题解 P5433 【月宫的符卡序列】

· · 题解

Q1：我们该选择什么算法？

首先看到题目的回文串 ，你的想法是不是回文自动机？

然而略加思索，回文自动机找的是回文串最后一个位置，而这道题的关键在于回文串中心位置，所以我们可以用Manacher

研究一下样例，会发现回文串的扩展符合Manacher扩展方式(可以对着数据模拟一下)

Q2：然后如何做呢？

我们都知道，最多有n个本质不同的回文串，因此当我们扩展到f[i]时，已经有了i种回文串。

然后？暴力扩展啊

就这样，我们扩展出了一个全新的回文串，这个回文串的基础是之前Manacher的回文串

这个回文串的基础

一个回文串必须由上一个回文串发展而来，你应该马上敏感地想到—— 拓扑排序

就这样，这里扩展出的回文串构成了一个拓扑序

Q3：然后是hash吗

Hash当然是很常见的选择

然而 单哈容易挂掉，双哈码量有些大……

因此，我们可以用pbds中hash探测法

点击进入日报详细学习

以O(N)的复杂度完成字符串类型的map（其实并不是真正的map，但你可以这么理解），码量小，还快得一批……

这样你就可以做这道题了

关键代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define N 3000005
#define ull unsigned long long
#define seed1 151
#define seed2 149
#define mod 19260817
#define mem(x) memset(x,0,sizeof(x))

void manacher()
{
    int i,len;
    len=1;
    a[0]='$';a[1]='#';
    for(register int i=1;i<=n;i++) {a[++len]=c[i];a[++len]='#';}
    a[len+1]='\0';int maxn=0,id=0,lasta=0;
    for(i=1;i<=len;i++)
    {
        if(maxn>i) p[i]=min(maxn-i,p[(id<<1)-i]);
        else p[i]=1;
        if(p[i]==1)lasta=0;
        else lasta=Map[change3(((i-p[i])>>1)+1,(i+p[i]-1)>>1)];
        while(a[i+p[i]]==a[i-p[i]])
        {
            p[i]++;
            int& temp=Map[change3(((i-p[i])>>1)+1,(i+p[i]-1)>>1)];
            if(!temp){temp=++tot;fa[tot]=lasta;sum[tot]=0;}
            lasta=temp;
        }
        sum[lasta]^=(i>>1)-1;
        if(i+p[i]>maxn){maxn=i+p[i];id=i;}
    }
}

void work()
{
    now1[0]=1;hash1[0]=0;
    for(register int i=1;i<=n;++i)
    {
        now1[i]=now1[i-1]*seed1%mod;
        hash1[i]=(hash1[i-1]*seed1+c[i])%mod;
    }
    now2[0]=1;hash2[0]=0;
    for(register int i=1;i<=n;++i)
    {
        now2[i]=now2[i-1]*seed2%mod;
        hash2[i]=(hash2[i-1]*seed2+c[i])%mod;
    }
    manacher();
}

最后，祝各位AC愉快