P8351

· · 题解

来 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)。