百度之星2022复赛题解

发表于 2022-09-15 分类于 XCPC

Astar2022 复赛 Solution.

A. 子序列

签到题。

显然，前面的递增条件完全没用。

答案就是所有数加起来。

时间复杂度 $O(n)$。

简单树形DP。

设 $f_{i,j,k}$ 表示以 $i$ 为根的子树中，与 $i$ 相连的连通块中，所有点与 $i$ 的最大距离为 $j$，连通块大小为 $k$ 的方案数。枚举与 $i$ 相连的每个点，选择是否与 $i$ 合并，然后DP即可。

时间复杂度 $O(nkm)$。

本题是本场比赛通过人数第二多的题。

答案即为 $n\times \sum_{i=1}^mi^{n-1}$。

当 $m\le B$ 时，暴力。时间复杂度 $O(m\log n)$。

当 $m>B$ 时，拉格朗日插值，或者求出伯努利数或第二类斯特林数算自然数幂和即可。时间复杂度 $O(n\log n)$。

取 $B=\sqrt{nm}$，时间复杂度 $O(\sqrt{nm}\log n)$。可适当调整块大小。

将询问按 $k$ 从小到大排序，设 $f_{l,r,0/1,1/1}$ 表示区间 $[l,r]$ 内子序列的开头是否 $<k$ ，结尾是否 $<k$ 的方案数。

动态DP，用线段树维护矩阵转移即可。

时间复杂度 $O((n+m)\log n)$。

设字符串总长为 $k$。

由 Polya 定理，答案为 $g(n)=\frac{\sum_{d|n}f(\frac{n}{d})\varphi(d)}{n}$。

其中 $f(m)$ 表示长度为 $m$ 的环，没有循环同构的答案。

可以发现，求出所有的 $f(m)$ 后，预处理欧拉函数

考虑反面，我们算出所有的不是好串的串。

那么建出所有串的Trie树，并构造出AC自动机。那么题目相当于在AC自动机上跳，不经过某个串的结尾的情况。

假设最后AC自动机在节点 $k$ 结束。因为有环，我们可以从一开始直接从节点 $k$ 开始走，然后最后必须在 $k$ 这里结束。

算出这个AC自动机的转移矩阵 $A$，可以发现，对于 $f(m)$，最终就是要求转移矩阵 $A$ 的 $m$ 次方的迹 $\text{tr}(A^m)$，即 $(A^m){1,1}+(A^m){2,2}+\cdots $。

直接算，复杂度 $O(n\times k^3)$，不足以通过。

可以使用以下的方法处理：

设 $w=\lfloor \sqrt{n} \rfloor$，预处理出：$A^0\sim A^w-1,A^{1\times w}\sim A^{\lceil \frac{n}{w} \rceil}\times w$，即可用 $O(k^2)$ 算出 $A^m$ 的迹。总的时间复杂度 $O(\sqrt{n}k^3+nk^2)$。

需要注意，当 $m$ 比较小时，不能将 $> m$ 的字符串扔进AC自动机里。

那么对于 $m\le 50$ 的答案，可以选择暴力重构AC自动机去计算 $f(m)$。

然后狄利克雷卷积算出所有的 $g$ 即可。总的时间复杂度 $O(nk^2+\sqrt{n}k^3+n\log n)$，足以通过本题。

建出SA，将 height数组按 $\geq k$ 的点分成若干段。

设 $f(m)=2^m-m-1$。

对于每个区间 $[l,r]$，设区间内的所有后缀在某个段里的个数是 $m$，那么其答案为所有这些段的 $f(m)$ 值的和。

莫队，维护这些和即可。

时间复杂度 $O(n\log n+n\sqrt{m})$。