自动搬运

查看原文

来自洛谷，原作者为

	tokitsukaze 网瘾很重，该电电了

搬运于2025-08-24 22:46:59，当前版本为作者最后更新于2023-05-06 11:20:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

本题核心是一个只要你学过回文树就知道的定理：一个长度为 $n$ 的字符串，本质不同回文子串的个数最多只有 $n$ 个。

根据题目这个条件：如果 $x$ 是回文串，那么假设 $y$ 是 $x$ 的前 $\frac{|x|+1}{2}$ 个字符组成的字符串 $f(x)=f(y)+1$，可知：

• 如果 $x$ 是回文串，$f(x)=f(y)+1$，如果 $y$ 又是回文串，那么要递归下去；而 $y$ 的长度是 $x$ 长度的一半，所以递归次数最多 $\log n$ 次（所以 $k$ 的范围最多只有 $30$）。

• 对于不同位置但本质相同的字符串，他们的 $f(x)$ 的值相同。

那么大致思路就出来了：枚举所有本质不同的回文串，分别对每种回文串 $x$，暴力递归求 $f(x)$（顺便记忆化一下），然后再计算出每种回文串在原串中出现了多少次，假设结果是 $cnt_x$，那么答案就可以这么计算： $ans_{f_x} \gets ans_{f_x} + cnt_x$。

这里提供一个使用回文树的实现方法：

int st[N][LOGN];
void init_ST()
{
	int i,j;
	for(i=2;i<tot;i++)
	{
		st[i][0]=fail[i];
		for(j=1;j<LOGN;j++)
		{
			st[i][j]=st[st[i][j-1]][j-1];
		}
	}
}
int get_substr(int l,int r)
{
	int now,tmp,i;
	now=pos[r];// pos[r] 表示以r为结尾的最长回文子串在回文树上的节点编号 
	
	// 倍增往fail跳 
	for(i=LOGN-1;~i;i--)
	{
		if(len[st[now][i]]>=r-l+1) now=st[now][i];
	}
	return now;
}
void count()
{
	// 计算每种回文串的出现次数 
	for(int i=tot-1;i;i--) cnt[fail[i]]+=cnt[i];
}
int f[MAX];
int dfs(int l,int r)// 记忆化求f(x) 
{
	// 获取子串[l,r]在回文树上的节点编号
	// 这里我用了倍增，似乎不用倍增也能过
	int now=get_substr(l,r);
	
	if(r-len[now]+1!=l) return 0; // 如果子串[l,r]不是回文串 f(x)=0 
	if(len[now]==1) return f[now]=1;
	if(len[now]<=0) return 0;// len[now]<=0 说明 now 是根节点 
	if(f[now]!=-1) return f[now];
	f[now]=dfs(l,r-len[now]/2)+1;
	return f[now];
}
ll ans[35];
void work(int n,int k)
{
	int i,l,r,now;
	count();
	init_ST();
	memset(f,-1,sizeof f);
	memset(ans,0,sizeof ans);
	for(i=1;i<=n;i++)
	{
		l=i-len[pos[i]]+1;
		r=i;
		// 以i为结尾的最长回文子串是[l,r]
		
		/*
		  这里为什么不需要枚举所有以i为结尾的回文串？
		   - 回文树的每个节点代表一种回文串
		   - 每次往回文树中新加入一个字符，最多只会创建一个新的节点
		  所以只需要求新的节点的f(x)即可
		*/
		dfs(l,r);
	}
	for(i=2;i<tot;i++) ans[f[i]]+=cnt[i];
	for(i=1;i<=k;i++) printf("%lld%c",ans[i]," \n"[i==k]);
}

记忆化求 $f(x)$ 的部分时间复杂度是 $O(n)$ 的，每次倍增找回文子串，时间复杂度 $O(\log n)$，所以总时间复杂度为 $O(n \log n)$。