CodeForces - 932G Palindrome Partition(回文自动机+Palindrome Series优化dp)

题目链接：点击查看

题目大意：给出一个长度为偶数的字符串，问将其分割成 k 个子串记为 a[ 1 ] , a[ 2 ] ... a[ k ] ，且满足 a[ i ] == a[ k - i + 1 ] 的方案数是多少

题目分析：一个不太容易证明的转换：

问题可以等价于，构造一个新的字符串 ss = s[ 1 ]s[ n ]s[ 2 ]s[ n - 1 ] ... s[ n/2 ]s[ n/2 + 1 ]，使得分割的每一部分都是偶回文串的方案数

分割问题不难想到一个 n * n 的 dp，直接用回文自动机转移即可，但很遗憾的是会超时

考虑优化，利用 Palindrome Series 可以将暴跳fail的时间复杂度优化成 logn，总时间复杂度优化成 O( nlogn )

代码：
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int N=1e6+100;

const int mod=1e9+7;
 
char s[N],t[N];

int n;

LL f[N],g[N];
 
struct Palindrome_tree
{
    int nxt[N][26];
    int fail[N]; // 当前节点最长回文后缀的节点
    int len[N]; // 当前节点表示的回文串的长度
    int cnt[N]; // 当前节点回文串的个数， 在getcnt后可得到全部
    int sed[N]; // 以当前节点为后缀的回文串的个数（并不是表示第i结尾的回文串的种类数，如果要求每个点结尾的数的回文串个数，得用last）
    int record[N]; //record记录了节点回文串的结束位置
    int diff[N],anc[N];
    char s[N];
    int tot; // 节点个数
    int last; // 上一个节点
    int n;//当前字符串的长度 
    void newnode()
    {
    	tot++;
    	memset(nxt[tot],0,sizeof(nxt[tot]));
    	cnt[tot]=sed[tot]=len[tot]=fail[tot]=0;
	}
    void init()
    {
    	n=0;
    	tot=-1;
    	newnode();
    	newnode();
        len[0] = 0, len[1] = -1; // 0为偶数长度根， 1为奇数长度根
        tot = 1, last = 0;
        fail[0] = 1;
    }
    int getfail(int x, int n)
    {
        while (s[n - len[x] - 1] != s[n]||n-len[x]-1<0) // 比较x节点回文串新建两端是否相等
        //n-len[x]-1<0这个是我自己加的，多组的时候光第一个条件是不够的，所以有错请手动删除
            x = fail[x]; // 若不同， 再比较x后缀回文串两端
        return x;
    }
    void insert(char ch)
    {
        int c = ch - 'a';//全小写要用a 全大写要用A 不然会错
        s[++n]=ch;
        int p = getfail(last, n);// 得到第i个字符可以加到哪个节点的两端形成回文串
        if (!nxt[p][c])
        {
        	newnode();
            len[tot] = len[p] + 2;  // 在p节点两端添加两个字符
            fail[tot] = nxt[getfail(fail[p], n)][c]; //tot点的后缀回文，可以由上一个节点的后缀回文尝试得到
            sed[tot] = sed[fail[tot]] + 1; // 以当前节点为结尾的回文串个数
            nxt[p][c] = tot; // 新建节点
            diff[tot]=len[tot]-len[fail[tot]];
            anc[tot]=diff[tot]==diff[fail[tot]]?anc[fail[tot]]:fail[tot];
        }
        last = nxt[p][c]; // 当前节点成为上一个节点
        cnt[last]++; //当前节点回文串++
        record[last] = n;
        trans(n);
    }
    void trans(int i)
	{
		for(int j=last;j>1;j=anc[j])
		{
			g[j]=f[i-len[anc[j]]-diff[j]];
			if(diff[j]==diff[fail[j]])
				g[j]=(g[j]+g[fail[j]])%mod; 
			f[i]=(f[i]+(i%2==0)*g[j])%mod;
		}
	}
    void get_cnt()
    {
        for (int i = tot; i > 0; i--)
            cnt[fail[i]] += cnt[i];
        //fail[i] 的节点 为 i 节点的后缀回文串， 所以个数相加
    }
}tree;

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	tree.init();
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n/2;i++)
	{
		t[2*i-1]=s[i];
		t[2*i]=s[n-i+1];
	}
	f[0]=1;
	for(int i=1;i<=n;i++)
		tree.insert(t[i]);
	printf("%lld\n",f[n]);













    return 0;
}