自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:38:18，当前版本为作者最后更新于2022-06-22 21:33:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

来 cnblogs 里看。

题出的好！难度不适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。

给出题人点赞 ！

题意

给定长度为 $n$ 的字符串 $s$。你有一个字符串 $t = s$，你每次操作可以在前面或在后面删除一个字符，直到字符串中只有一个字符。设每次操作后得到的字符串分别是 $a_1,a_2,..,a_{n-1}$，那么这种操作的权值就是 $\prod_{1 \le i < n} occ(a_i)$。其中 $occ(a)$ 表示字符串 $a$ 在 $s$ 中的出现次数。求对于所有操作序列的权值和。

数据范围：$n \le 10^5$

题解

首先考虑一下有哪些本质不同的串，满足从左边或右边删除一个字符，能使得在整个串中出现的次数变大了。称这样的串为 "好串"。

不妨仅考虑从左删除一个字符，有多少出现次数变了：只有 $\text{parent tree}$ 的节点 $x$ 上，长度恰好为 $maxlen_{fa_x}+1$ 的串。因此满足这种条件的串只有 $\Theta(n)$ 个。

我们把 "好串" 和 "好串" 从前或从后删除一个字符后得到的串称为 "关键串"。我们已经知道了出现次数不同的串之间的转移了，因此现在我们只用关心出现次数相同的关键串之间的转移了。

我们只关心每个串第一次出现时的位置。由于每个串在整个串中出现的次数相同，因此这样做，串间的包含关系不变。

接下来我们就可以写一份暴力了，可以直接树状数组暴力枚举每个串 $[l,r]$ 的子串 $[x,y]$，从 $[l,r]$ 走到 $[x,y]$ 的权值是 $\binom{x-l+r-y}{x-l} c^{r-l+1} c^{-(y-x)}$。这样可以拿到 $40$ 分。

考虑优化。我们显然可以把 $c^{r-l+1} c^{-(y-x)}$ 直接在两个区间处直接处理掉，因此我们就只用考虑从 $[l,r]$ 走到 $[x,y]$ 的方案数了。

直接算方案数很难算，我们不妨先打个表看看关键串出现的位置有没有什么规律：

可以发现，对于每种颜色的每一块，围成的区域很规整。可以看作是一个长度为 $m$ 的序列 $a$ 满足 $a_{i} \le a_{i+1}$，表示有 $i$ 列，第 $i$ 列从上到下有连续 $a_i$ 个元素。

为什么是这个形状的呢？首先容易发现如果一个点下面和右边都在连通块内，那么这个点也在连通块内。

其次就是这个图形满足只有一个点是 "极点" 的（也就是满足上面和右边都不在连通块内），这个可以考虑如果存在两个，这两个同时包含串 $t$，而这两个串不相交，说明串 $t$ 的出现次数并不一样。因此就只有一个 "极点" 了。

接下来考虑怎么求解。我们要从右上角的元素转移到左下角边界上的元素。这个东西可以用类似 gym102978J 的分治算法，每次取出 $mid$ 划分，中间用 $4$ 次卷积转移，然后分裂成两个问题。具体如下图：

时间复杂度 $\Theta(n \log^2 n)$。