ICM Technex 2018 and Codeforces Round #463-- G、Palindrome Partition（回文自动机）

题目链接

题面：

题意：
给定一个字符串，把字符串分为偶数段，假设分为了 $k$k段，那么需要满足 $s_1=s_k,s2=s_{k-1}...$s1​=sk​,s2=sk−1​...。
求符合要求的划分的方案数。

题解：
我们假设原串为 $S$S，长度为 $n$n

假设现在有两段 $s_i,s_{k-i+1}$si​,sk−i+1​，其中 $s_i=s_{k-i+1}=x_1{x}_2...x_j$si​=sk−i+1​=x1​x2​...xj​。

假设 $S_i$Si​的起始位置为 $p$p，那么有:
$s_i=S\left[p\right]S[p+1]...S[p+j-1]$si​=S[p]S[p+1]...S[p+j−1]

$s_{k-i+1}=S[n-j-p+2]S[n-j-p+2]...S[n-p+1]$sk−i+1​=S[n−j−p+2]S[n−j−p+2]...S[n−p+1]。

对应相等关系即： $S\left[p\right]=S[n-p-j+2]$S[p]=S[n−p−j+2]

我们令 $p=1$p=1，那么有 $S\left[1\right]=S[n-j+1]$S[1]=S[n−j+1]

那么假设我们现在有一个串 $T$T， $T=S\left[1\right]S\left[n\right]S\left[2\right]S[n-2]...$T=S[1]S[n]S[2]S[n−2]...

那么对应到上面的关系里面，就是 $T[\mathrm{1...2}\ast j]$T[1...2∗j]是一个回文串。

可以证明，对于任意 $p=i,i\in [1,k]$p=i,i∈[1,k]，都需要满足其对应的那一段为回文串。

题目转化为：
已知一个串 $T$T，把 $T$T划分为若干个长度为偶数的回文串的方法。

$dp$dp 转移方程显然。

代码：
这是错误代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-5;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxp=1100;
const int maxm=4000100;
const int up=1000;
const int N=26;

struct Palindromic_Tree
{
    int t[maxn][N];
    int fail[maxn];
    int cnt[maxn];
    int num[maxn];
    int len[maxn];
    int S[maxn];
    int last;
    int n;
    int p;

    int newnode(int l)
    {
        for(int i=0;i<N;++i) t[p][i]=0;
        cnt[p]=0;
        num[p]=0;
        len[p]=l;
        return p++;
    }

    void init(void)
    {
        p=0;
        newnode(0);
        newnode(-1);
        last=0;
        n=0;
        S[n]=-1;
        fail[0]=1;
    }

    int get_fail(int x)
    {
        while(S[n-len[x]-1]!=S[n]) x=fail[x];
        return x;
    }

    void add(int c)
    {
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);
        if(!t[cur][c])
        {
            int now=newnode(len[cur]+2);
            fail[now]=t[get_fail(fail[cur])][c];
            t[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=t[cur][c];
        cnt[last]++;
    }

    void _count(void)
    {
        for(int i=p-1;i>=0;--i) cnt[fail[i]]+=cnt[i];
    }
}pam;

int dp[maxn];
char str[maxn],s[maxn];

int main(void)
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    if(n&1)
    {
        printf("0\n");
        return 0;
    }
    int cnt=0;
    int l=1,r=n;
    for(int i=1;i<=n/2;i++)
        s[++cnt]=str[l++],s[++cnt]=str[r--];

    pam.init();
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        pam.add(s[i]);
        int p=pam.last;
        while(p!=0&&p!=1)
        {
            if(pam.len[p]%2==0) dp[i]=(dp[i]+dp[i-pam.len[p]])%mod;
            p=pam.fail[p];
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}

TLE在Test41。

分析一下为什么会T，其实对于一个长度为n的由一个字符组成的字符串，每次暴跳 fail 指针的时间复杂度是 $O\left(n^2\right)$O(n2)。

刚刚学习到，从某一节点暴跳 $fail$fail 时，所经过的节点所表示的回文串都是当前串的 $border$border，那么他们可以分为 $logn$logn 个等差数列。
若 $fail$fail 到根可以分组处理（每组是一个等差数列），那么暴跳 $fail$fail 的时间复杂度就会从 $O\left(n\right)$O(n) 降到 $O\left(logn\right)$O(logn)。

我们设 $g\left[x\right]$g[x] 为回文树节点为 $x$x 跳 $fail$fail 所经过的节点得到的等差回文串的贡献。
当前插入串 $T\left[\mathrm{1...}i\right]$T[1...i]，插入完 $T\left[i\right]$T[i]后的节点为 $x$x

我们设当前的等差回文后缀长度为 $b_1,b_2,b_3$b1​,b2​,b3​，其中 $b_1>b_2>b_3$b1​>b2​>b3​，公差为 $d$d。
那么我们知道 $g\left[x\right]=f[i-b_1]+f[i-b_2]+f[i-b_3]$g[x]=f[i−b1​]+f[i−b2​]+f[i−b3​]，其中 $f\left[x\right]$f[x]就是前一种方法的 $dp$dp。
现在有 $fail\left[b_1\right]=b2,fail\left[b_2\right]=b3$fail[b1​]=b2,fail[b2​]=b3

由回文串的性质，可得:
$T[i-b_1+1,i-d]=T[i-d-b_2+1,i-d]=T[i-b_2+1,i]$T[i−b1​+1,i−d]=T[i−d−b2​+1,i−d]=T[i−b2​+1,i]
$T[i-b_2+1,i-d]=T[i-d-b_3+1,i-d]=T[i-b_3+1,i]$T[i−b2​+1,i−d]=T[i−d−b3​+1,i−d]=T[i−b3​+1,i]

$g\left[fail\right[x\left]\right]=f[i-d-b_2]+f[i-d-b_3]=f[i-b_1]+f[i-b_2]$g[fail[x]]=f[i−d−b2​]+f[i−d−b3​]=f[i−b1​]+f[i−b2​]

所以：
$g\left[x\right]=g\left[fail\right[x\left]\right]+f[i-b_3]，f[i-b_3]$g[x]=g[fail[x]]+f[i−b3​]，f[i−b3​]是当前节点往前等差数列最小的一项。其中 $fail\left[x\right]与x$fail[x]与x 应处于同一个等差数列中。

时间复杂度 $O\left(nlogn\right)$O(nlogn)
代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-5;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxp=1100;
const int maxm=4000100;
const int up=1000;
const int N=26;

struct Palindromic_Tree
{
    int t[maxn][N];
    int fail[maxn];
    int cnt[maxn];
    int num[maxn];
    int len[maxn];
    int S[maxn];
    int di[maxn];//节点x与fail[x]长度之差
    int pre[maxn];//上一个等差序列的最后一项。
    int last;
    int n;
    int p;

    int newnode(int l)
    {
        for(int i=0;i<N;++i) t[p][i]=0;
        cnt[p]=0;
        num[p]=0;
        len[p]=l;
        return p++;
    }

    void init(void)
    {
        p=0;
        newnode(0);
        newnode(-1);
        last=0;
        n=0;
        S[n]=-1;
        fail[0]=1;
        pre[0]=1;
    }

    int get_fail(int x)
    {
        while(S[n-len[x]-1]!=S[n]) x=fail[x];
        return x;
    }

    void add(int c)
    {
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);
        if(!t[cur][c])
        {
            int now=newnode(len[cur]+2);
            fail[now]=t[get_fail(fail[cur])][c];
            t[cur][c]=now;
            num[now]=num[fail[now]]+1;
            di[now]=len[now]-len[fail[now]];
            pre[now]=(di[now]==di[fail[now]])?pre[fail[now]]:fail[now];
        }
        last=t[cur][c];
        cnt[last]++;
    }

    void _count(void)
    {
        for(int i=p-1;i>=0;--i) cnt[fail[i]]+=cnt[i];
    }
}pam;

int dp[maxn],g[maxn];
char str[maxn],s[maxn];

int main(void)
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    if(n&1)
    {
        printf("0\n");
        return 0;
    }
    int cnt=0;
    int l=1,r=n;
    for(int i=1;i<=n/2;i++)
        s[++cnt]=str[l++],s[++cnt]=str[r--];

    pam.init();
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        pam.add(s[i]);
        for(int p=pam.last;p!=1&&p!=0;p=pam.pre[p])
        {
        	//这里，假设border长度为 1 2 3 4 6 8 10，那么pre[id(10)]=id(4)
        	//因为1 2 3 4等差，6 8 10 等差。
        	//后一个等差数列的第一项与前一个等差数列的最后一项相差的是后一个等差数列的公差。
            g[p]=dp[i-pam.len[pam.pre[p]]-pam.di[p]];
            if(pam.fail[p]!=pam.pre[p])
                g[p]=(g[p]+g[pam.fail[p]])%mod;
            //只计算长度为偶数的回文串
            if(i%2==0) dp[i]=(dp[i]+g[p])%mod;
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}