诗歌 expected version 题解
Zzzcr
·
·
算法·理论
将查询的单序列求单项，改成双序列单点卷积。
本题解中记 N 为所有询问中 n 的最大值。
Observation 1: 容易发现，只需要考虑长度为 2 或 3 的回文串即可。
换句话说，一个串是「动听」的，当且仅当对于任意两个相同的字符，它们的下标之差大于 m+2。
Observation 2: 若一个字符串是「动听」的，则它的每个前缀都是「动听」的。
对于所有长度为 n 的「动听」字符串，只需要在所有长度为 n-1 的「动听」字符串后添加字符即可得到，这启发我们把所有「动听」的字符串建成一颗 trie。
在每个 trie 的叶子节点上添加新节点的过程中，需要满足 trie 上不存在一条长度为 m+3 的、首尾存在相同字符的链。
考虑这颗 trie 的形态，它形如一个长度为 m+2 的链下挂一个完全 k-m-2 叉树，f(T,U,n) 也就是 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|)。我们在这里继续沿用这种思路，对上述矩阵做法逐步优化。
为了方便表述，下面我们称 f(T_1,U_1,n) 为 f_n，f(T_2,U_2,n) 为 g_n，下文中很多地方只考虑了 f，g 的推导是一样的。
前 \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)。在这里使用 \mathcal{O}(m^2) 会给复杂度加一个瓶颈，但在本题数据范围下是可以接受的。
对于后面的转移，可以写作：
f_n=\sum a_i f_{n-i}+\lambda^{n-m-3}|U|,
其中 \lambda,a_i 对每组参数不变。
考虑构造辅助序列 r，使得
r_n
=
\sum \frac{a_i r_{n-i}}{\lambda^i}
+\frac{|U|}{\lambda^{m+3}}
=
\frac{-1}{\lambda}\sum r_{n-i}
+\frac{|U|}{\lambda^{m+3}}.
即
f_n-r_n\lambda^n
=
\sum a_i(f_{n-i}-r_{n-i}\lambda^{n-i}).
所以只需要对 f_i-r_i\lambda^i 进行线性递推即可。
设 F(x) 为上述齐次线性递推的特征多项式，那么 f,g 都可以表示成特征多项式为 F(x) 的线性递推序列。设它们的生成函数分别为 \frac{P_f(x)}{F(x)} 和 \frac{P_g(x)}{F(x)}，记 h_n=\sum_{i=0}^{n}f_i g_{n-i}，那么 h 的生成函数就是两个生成函数的乘积：
\left(\sum_{n\ge0}f_nx^n\right)
\left(\sum_{n\ge0}g_nx^n\right)
=
\frac{P_f(x)}{F(x)}
\cdot
\frac{P_g(x)}{F(x)}.
\sum_{n\ge0}h_nx^n
=
\frac{P_f(x)P_g(x)}{F^2(x)}.
原题中单个序列的特征多项式为 F(x)，现在卷积序列 h 的特征多项式变成了 F^2(x),那么 h 满足一个 2\deg F 阶的齐次线性递推。
现在需要求出 h 的前 2d 项，取 f,g 的前 2d 项做一次 NTT 即可。
查询第 n 项时，原来的做法需要计算 x^{n-m-3}\bmod F(x)，现在只需要把模数换成 F^2(x)，也就是 x^{n-m-3}\bmod F^2(x)，利用得到的多项式与 h 的前 2d 项做线性组合，即可得到答案。
由于 F^2 仍然只有常数个非零项，对其求逆只需要线性的时间，对此可以参考原题题解。
最终复杂度仍然为 \mathcal O\left(qm\log m+N+\sum |U|\right)。