ZigZagK的博客
[思维+Palindrome Series]Codeforces932G【Palindrome Partition】题解
2022年10月12日 20:27
查看标签

题目概述

CF932G

解题报告

首先原题意有点恐怖,我们需要进行一定的转化。原题意需要分成偶数个串,然后前后对称相同,如果我们把串的后一半翻转,那么就会发现前后对应的两个字符串是互相翻转的。

进一步转化,如果 $A$ 和 $B$ 互相翻转,那么穿插接起来显然是一个偶数长度的回文串,如:$ab|cd|cd|ab$ 后面翻转后为 $ab|cd|ba|dc$ ,就变成了 $ab$ 和 $ba$ ,$cd$ 和 $dc$ 对应,穿插起来之后就是 $abba,cddc$ 即两个回文串。

因此原题意转化为,把字符串后一半翻转,穿插进前一半,然后求多少种方案把新字符串分成偶数长度的回文串。


定义 $f_i$ 表示 $[1,i]$ 分成回文串的方案数,不难想到枚举以 $i$ 结尾的回文串进行转移,可以利用PAM:

$$ f_i=\sum\{f_j|S[j+1,i]\text{ is Palindrome}\} $$

但是这显然是 $O(n^2)$ 的,无法接受,因此我们需要用到一个PAM科技Palindrome Series。

推荐博客:Border Series在回文自动机上的运用字符串科技:Palindrome SeriesA bit more about palindromes

这里就介绍和解释几个关键结论:

  1. 一个串的长度在 $[2^k,2^{k+1})$ 范围内的Border长度构成等差数列(Border Series)。
  2. 字符串 $T$ 是回文串 $S$ 的一个回文后缀,当且仅当 $T$ 是 $S$ 的Border。

    回文后缀一定也是回文前缀,因此满足Border性质。

  3. 字符串 $S$ 存在回文Border $T$ ,且 $|T|\ge{|S|\over 2}$ ,则 $S$ 是回文串。

    即 $S$ 前 $|T|$ 个字符构成回文,后 $|T|$ 个字符也构成回文,且这两个串覆盖整个串,因此 $S$ 是回文串。

根据结论2,回文自动机上 $x$ 节点在 $fail$ 树上的所有祖先都是 $x$ 对应串的Border。


在PAM上额外维护以下信息:

  1. $dif_x=len_x-len_{fail_x}$ ,即 $x$ 与 $fail_x$ 最长Border的差,也就是所在等差数列的公差。
  2. $anc_x$ 表示 $x$ 往上遇到的第一个 $dif_p\not=dif_{fail_p}$ 的 $p$ 的父亲,即所在等差数列的顶点的父亲。

    结论4:如果 $dif_x>{len_x\over 2}$ ,则 $anc_x=fail_x$ 。因为 $len_x$ 显然不可能再减一次 $dif_x$ 。

    结论5:如果 $dif_x=dif_{fail_x}$ ,则 $len_{fail_x}\ge{len_x\over 2}$ 。由结论4易得。

  3. $sum_x$ 表示 $[x,anc_x)$ 路径上的当前信息(包含 $x$ ,不包含 $anc_x$ )。

$sum$ 是动态维护的,某一时刻并不是所有 $sum$ 都有意义。假设当前插入了 $S[1,i]$ ,停在 $x$ 节点,则:

$$ sum_x=\sum\{f_{i-len_x},f_{i-len_{fail_x}},\cdots,f_{i-len_t}\},fail_t=anc_x $$

这样的话,我们只要不停的跳转 $x$ 到 $anc_x$ 就可以统计出 $f_i$ 答案,问题是如何维护。

接下来证明一个重要结论,按照上述过程,处理到 $x$ 时,$fail_x$(如果在路径上的话)一定已经在 $j=i-dif_x$ 时被处理过了。

$$ sum_{fail_x}=\sum\{f_{j-len_{fail_x}},\cdots,f_{j-len_t}\},fail_t=anc_x $$

首先证明,$fail_x$ 的最后一次出现位置在 $i-dif_x$ :

由于 $fail_x$ 是 $x$ 的Border,因此 $i-dif_x$ 是一个出现位置,只需要证明 $[i-dif_x+1,i-1]$ 没有出现。

利用反证法:假设出现在了 $k$ ,根据结论5,$i-dif_x$ 的串和 $k$ 的串一定是接触的,则根据结论3,这两个串合起来也是回文串,且是 $x$ 的回文前缀即回文后缀,也就是说,$fail_x$ 并不是 $x$ 的最长回文后缀,这与定义不符,因此不存在 $k$ 。

接下来证明,$fail_x$ 一定在 $i-dif_x$ 时被更新过了:

假设在 $i-dif_x$ 时,存在一个 $fail_x$ 所在等差链的子节点 $p$ ,则 $fail_p=fail_x,len_p=len_{fail_x}+dif_x$ 。

即 $fail_x$ 往前添加 $dif_x$ 个字符之后是回文串,但是由于 $fail_x$ 是 $x$ 的回文前缀且长度也少 $dif_x$ ,根据Border和回文串的性质,易得 $x$ 往前添加 $dif_x$ 个字符也是回文串,这与当前处理到的 $x$ 定义不符( $x$ 是链底或者 $x$ 是 $i$ 结尾的最长回文后缀)。

因此 $fail_x$ 一定是 $i-dif_x$ 时的链底(或者 $i-dif_x$ 的最长回文后缀),也就是说已经维护过了。

结论6:更新 $i$ 信息时,需要用到的 $sum$ 一定已经被更新过了。


我们观察 $sum_{fail_x}$ ,由于 $j=i-dif_x,len_x=len_{fail_x}+dif_x$ ,因此 $i-len_x=j-len_{fail_x}$ ,以此类推,$sum_{fail_x}$ 的所有项都在 $sum_x$ 中出现过,除了 $f_{i-len_t}$ ,因此只需要补上这一个即可,即:

$$ sum_x=sum_{fail_x}+f_{i-len_t},fail_t=anc_x $$

接下来说明复杂度:

结论7:$len_{anc_x}\le{len_x\over 2}$ 。由结论1可知,$x$ 到 $anc_x$ 时 $[2^k,2^{k+1})$ 的 $k$ 至少减一,因此长度至少减半。

因此 $x$ 沿着 $anc_x$ 只会跳 $\log_2n$ 次,更新 $sum$ 的复杂度为 $O(\log_2n)$ 。

对于这道题,由于只要偶数长度回文串,因此 $f_i$ 只允许偶数位置上有值。

示例程序

讲了这么多,代码就是PAM上加点东西,非常好写。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000,maxi=26,MOD=1e9+7;

int n;char s[maxn+5],t[maxn+5];
int pl,son[maxn+5][maxi],len[maxn+5],fai[maxn+5];
int dif[maxn+5],anc[maxn+5],sum[maxn+5];
int f[maxn+5];

inline int newnode() {pl++;return pl;}
int Extend(int p,char *s,int i){
    while (s[i]!=s[i-len[p]-1]) p=fai[p];
    if (!son[p][s[i]-'a']){
        int u=newnode(),k=fai[p];len[u]=len[p]+2;
        while (s[i]!=s[i-len[k]-1]) k=fai[k];
        fai[u]=son[k][s[i]-'a'];son[p][s[i]-'a']=u;
        dif[u]=len[u]-len[fai[u]];
        anc[u]=(dif[u]==dif[fai[u]]?anc[fai[u]]:fai[u]);
    }
    p=son[p][s[i]-'a'];
    return p;
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
int main(){
    scanf("%s",t+1);n=strlen(t+1);
    for (int i=1,L=1,R=n;i<=n;i+=2,L++,R--) s[i]=t[L],s[i+1]=t[R];
    pl=-1;newnode();newnode();
    fai[0]=fai[1]=1;len[0]=0;len[1]=-1;
    f[0]=1;
    for (int i=1,p=0;i<=n;i++){
        p=Extend(p,s,i);
        for (int x=p;x>1;x=anc[x]){
            sum[x]=f[i-(len[anc[x]]+dif[x])];
            if (dif[x]==dif[fai[x]]) sum[x]=ADD(sum[x],sum[fai[x]]);
            if (i&1^1) f[i]=ADD(f[i],sum[x]);
        }
    }
    printf("%d\n",f[n]);
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!