自动搬运

查看原文

来自洛谷，原作者为

	Zzzcr **

搬运于2025-08-24 23:11:39，当前版本为作者最后更新于2025-03-22 20:35:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

注：这是一个小丑做法，若只是为通过此题不建议学习该题解。

本题解中记 $N$ 为所有询问中 $n$ 的最大值。

Observation 1: 容易发现，只需要考虑长度为 $2$ 或 $3$ 的回文串即可。

换句话说，一个串是动听的，当且仅当对于任意两个相同的字符，它们的下标之差大于 $m+2$。

Observation 2: 若一个字符串是「动听」的，则它的每个前缀都是「动听」的。

对于所有长度为 $n$ 的「动听」字符串，只需要在所有长度为 $n-1$ 的「动听」字符串后添加字符即可得到，这启发我们把所有「动听」的字符串建成一颗 trie。在每个 trie 的叶子节点上添加新节点的过程中，同时需要满足 trie 上不存在一条长度为 $m + 3$ 的存在相同字符的链。

考虑这颗 trie 的形态，它形如一个长度为 $m + 2$ 的链下挂一个完全 $k - m - 2$ 叉树。

本题所求的也就是 trie 上深度为 $n$ 且该字符属于 $U$ 的节点数量，注意到每一层的答案只与上一层总儿子数量和前 $m - 2$ 层的答案有关，可以 $\mathcal{O}(\sum{|U|}nm)$ 暴力 dp。

考虑把上述 dp 柿子记成矩阵形式，需要注意的是前 $m + 1$ 个转移与其他的转移并不相同，直接暴力转移，用倍增预处理出矩阵 $2^k$ 次幂，再把把初始向量叠加在一起，可以做到 $\mathcal{O}(qm^2\log n+m^3\log N+\sum{|U|})$。

---

考虑对上述过程逐步优化。

前 $\mathcal{O}(m)$ 次转移比较特殊，可以对这些转移的前缀预处理出系数矩阵 $p$，系数向量 $C$，使得 $f_k=\sum_{i=1}^{m+2} p_{k,i}f_i+|U|C_k$。具体的可以观察多项式之间的系数关系，对其分段。如何获得最终向量呢？实际上，这相当于选定一些关键列后对每行求和，观察矩阵 $p$，注意到它的每一列都可以拆成至多 2 段比值相同的等比数列，可以用扫描线做到关于 $|U|$ 线性。现在只需要 $p$ 中每列分界点的值了，容易发现这样的元素只有 $\mathcal{O}(m)$ 个，预处理可以做到 $\mathcal{O}(m)$。

本题式子可以写作 $f_n=\sum a_if_{n-i}+h^{n-m-3}\cdot |U|$，其中 $h,a_i$ 对每组询问不变。比常系数齐次线性递推多了一项幂函数。考虑构造序列 $g$，使得 $g_n=\sum \frac{a_ig_{n-i}}{h^i}+\frac{|U|}{h^{m+3}}=\frac {-1} h\sum g_{n-i}+\frac{|U|}{h^{m+3}}$，即 $f_n-g_nh^n=\sum a_i(f_{n-i}-g_{n-i}h^{n-i})$，所以只需要对 $f_i-g_ih^i$ 线性递推即可。

查询时只需要 $g$ 的前 $\mathcal{O}(m)$ 项和第 $n$ 项，前者可以询问时处理，后者的问题与求 $f_n-g_nh^n$ 是类似的，可以仿照下面对 $f_i-g_ih^i$ 线性递推的方式来做。

每次询问只有 $n$ 和初始向量不同。设 $F(x)$ 为转移的特征多项式，根据线性递推的过程，我们需要 $x^{n-m-3}\bmod F(x)\bmod x^{\mathcal{O}(m)}$，每次询问做一个 NTT 即可。预处理多项式求逆可以做到线性。具体的，考虑 $f(x)=1+ax+bx^t$ 的逆，记 $c_p=[x^p]f^{-1}(x)$，有

$$c_p=\left\{\begin{matrix} (-a)^p\ (p<t)\\ -c_{p-1}\cdot a-c_{i-t}\cdot b\ (p\ge t)\\ \end{matrix}\right. $$

复杂度 $\mathcal{O}(N)\sim \mathcal{O}(m\log m)$。

最终我们做到了 $\mathcal{O}(qm\log m+N+\sum|U|)$。实现细节有点多，需要注意一下代码常数。