P11959「ZHQOI R1」诗歌 题解

Zzzcr · 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)，有

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

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