题解-SDOI/SXOI2022 子串统计

本文主要是介绍题解-SDOI/SXOI2022 子串统计，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

给出题人点赞 ！

感觉做这题做得挺开心的。

题意

给定长度为 \(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\) 个元素。我们要从右上角的元素转移到左下角边界上的元素。

这个东西可以用类似 Japanese Knowledge 的分治算法，每次取出 \(mid\) 划分，中间用 \(4\) 次 DFT 转移，然后分裂成两个问题。具体如下图：

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

这篇关于题解-SDOI/SXOI2022 子串统计的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！