P8351 [SDOI/SXOI2022] 子串统计

· · 题解

题传

细节好多/px

考虑 naive 的 O(n^{2}) DP，设 f_{[l, r]} 表示当前串为 [l, r] 的路径权值和，答案即为 \sum f_{[i, i]}。

我们考虑基本子串结构，注意到本题本质上在统计从点阵左上角到 y=x 的所有路径经过的点的 \operatorname{occ} 乘积的和。贡献分布在 y=x 上不好算，考虑将路径全部反向统计到左上角 (1, n)。

若将 f 刷表出来，一个等价类 a 在图上出现的若干位置 G(a) 全部相等，所以考虑将等价类之间的包含关系建出一张 DAG 倒拓扑序处理等价类，得到了一个常数略小的 O(n^{2}) 做法。

发现我们的复杂度瓶颈在于等价类内部的 f 转移，而对于不同等价类之间的转移需要用的只有等价类的上边界和左边界。

考虑分治求每个等价类代表的阶梯图的左边界和上边界，每次我们选择长宽中更长的一部分折半，根据下面的部分切出一条平行于另一边的线，将所求的 f 数组划分为三个部分，两个阶梯状的子图递归解决。

处理完子问题后，对于中间的矩形 (a, b)-(c, d) 部分，我们得到其右边界和下边界的 f，我们希望快速得到上边界和左边界。设 k 为等价类 a 的出现次数。

下边界转移到上边界：

f_{b, y}\binom{y-x+b-a}{b-a}k^{y-x+b-a}\to f_{a, x}(x\le y)

展开：

f_{b, y}\frac{(y-x+b-a)!}{(b-a)!(y-x)!}k^{y-x+b-a}\to f_{a, x}

不难发现这是个减法卷积的形式。

下边界转移到左边界：

f_{b, y}\binom {x-a+d-y}{x-a}k^{x-a+d-y}\to f_{x, b} f_{b, y}\frac {(x-a+d-y)!}{(x-a)!(d-y)!}k^{x-a+d-y}\to f_{x, b}

同样也可以减法卷积，右边界的转移同理。

于是一层分治 + 4 次卷积即可，卷积的长度不超过等价类行数和列数和（不超过 2n），复杂度 O(n\log ^2 n)。

实现细节：阶乘和 k 的幂的处理要到两倍，递归后得到的数组其实是右边界右边一列 + 下边界下一列，注意 +1 之类的边界问题。

Code

我的写法常数相当大，通过预处理单位根的幂可以在 2s 内极限在 lg 过。Code2。