Loj#6703 小 Q 的序列

发表于 分类于 ， ， 阅读次数：

题意：定义一个序列 的权值为 。给出一个长度为 的序列，求所有 个非空子序列的权值和。

答案对 取模， ，时限 。

考虑 DP，设 为前 个位置已经选定 个位置的权值和。有转移 令 （第 行的生成函数）。

我们希望递推式中的次数能尽量对齐，但注意到 这一项系数复杂，却没有和 对齐，不便处理。不妨将 翻转（即 ），易得递推式 记 ，写出多项式形式的转移（边界是 ）

有两种方法处理这个递推式。

（方法一） 其中算子 满足 。

算子 和 之间没有交换律，但具有线性性，故和常数有交换律，而且和多项式有分配率。可得 分治 FFT 计算 ，（根据 的分配率）则 其中 是对 施加 次 的结果，是个多项式。

我们需要求 的系数和，只需对 求出 的系数之和即可。设 ，则有递推式 这正是带符号第二类斯特林数，接下来的任务是《多项式和递推》的【例题 6.4.8】。

复杂度可以做到 或 。

（方法二）直接处理 的递推式。三项不便处理，考虑使用附加因子法将其中两项合并。构造 ，则 考虑系数，可得 构造 ，然后多点求值即可对 求出各个 ，复杂度 。这样可以求出 的各项系数，而不仅是得到 。

这一思路扩展性较强，例： 求出二维 的一项。（HDU 多校 2023 Round6 1007 Competition）