题解

给定一个长度为$n(n \leq 10^6)$的字符串$S$，求其中的回文套娃个数。回文套娃定义为两个序列$l_1<l_2<…<l_k$和$r_1>r_2>…>r_k$，其中每个$S[l_i:r_i]$均为回文串。

在回文树中，每个节点$x$代表的字符串有两个前驱，第一个是删除第一个和最后一个字符得到的父亲节点$fa(x)$，第二个是最长前/后缀所代表的节点$f(x)$。

对于每个回文串$s[l:r]$，其包含的回文子串$s[x:y]$都可以通过如下的方式不重不漏地访问：先跳若干步$fa$，直到$l==x$或$r==y$。此时$s[x:y]$一定是$s[l:r]$的前缀或者后缀，所以再连续跳若干步最长前缀或者跳若干步最长后缀即可（此步骤中不能既跳前缀又跳后缀，否则将不满足$l==x$或$r==y$，此时得到的串将会被重复访问）。

我们设$ff(x)$表示一定选节点$x$所代表的字符串，且该字符串是套娃的最外层的方案数。那么枚举其包含的每个回文子串$y$，可得到$ff(x)=(\sum ff(y))+1$。简化方法即分别记录两种前驱的前缀和进行运算，详见以下代码。最后枚举右端点，将当前右端点所对应的所有回文串作为最外层套娃的方案数计入答案中即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 998244353;

char s[N];
int n;
int ans;

struct PalindromesTree{
	int tot,last,l[N],son[N][26],c[N],f[N];
	ll ff[N];
	ll pref[N],prefa[N]; 

	int newnode(int x){
		l[++tot]=x;
		return tot;
	}
	
	void init(){
		tot=-1;last=0;
		f[newnode(0)]=1;
		f[newnode(-1)]=0;
	}
	
	int get(int x,int n){
		while(s[n]!=s[n-l[x]-1])x=f[x];
		return x;
	}
	
	void add(int x,int i){
		int y=get(last,i);
		if(!son[y][x]){
			int now=newnode(l[y]+2),ne=get(f[y],i);
			f[now]=son[ne][x];
			son[y][x]=now;
			//y是删去左右第一个字符的父亲节点
			//f[now]是最长回文前/后缀代表的节点
			//ff[now]即now作为最外层套娃且必选now的方案数
			//pref是f作为前驱的ff前缀和
			//prefa是fa作为前去的ff前缀和
			ff[now]=(prefa[y]+1)%mod;
			pref[now]=(pref[f[now]]+ff[now])%mod;
			prefa[now]=(prefa[y]+2*pref[f[now]]+ff[now])%mod;
			//在跳若干次父亲节点后，第一次跳f时，有跳前缀和跳后缀两种方案，所以此处要*2
		}
		last=son[y][x];
		(ans+=pref[son[y][x]])%=mod;
	}
	
	void solve(){
		for(int i=1;i<=n;++i)add(s[i]-'a',i);
	}
}T;

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	T.init();
	T.solve();
	printf("%d\n",ans);
}