Luogu7342 『MdOI R4』Destiny

题意：一个长度为 的序列 的权值 定义为：

• 时为 。

• 时为它所有子区间的权值之和，也就是

给定一个序列 ，求它的的权值。这个序列非常长，是这样生成的：输入序列 ，令 。

答案对 取模，，，时限 。

---

设 表示长度为 的序列中第 个位置的贡献系数。计算 时，考虑每个覆盖 的区间 的贡献。分别枚举 ，可得

设 ，不难得到递推

结合 可得

这个递推式非常漂亮，系数都是常数。

---

设 ，即第 行的 OGF。

则有生成函数形式的递推式

可以视作（多项式的）二阶线性递推，边界为 。

答案为 于是，我们只需求出 （即进行长度为 的循环卷积），即可得到答案。

用矩阵快速幂优化线性递推的计算（ 矩阵中的元素是长度至多为 的多项式），复杂度 。（也可以用特征方程解决）

---

具体计算如下：

为了凑一个好看的式子（减小常数），钦定 ，最后特判。

利用特征方程可解得

使用循环卷积快速幂即可。但循环卷积中没有除法，定义式分母中的 难以去除。实际上， 的循环多项式也没有好的定义。

考虑扩域，维护形为 的多项式，然后利用 来计算。

由于计算 的幂次时， 中 总是有限多项式，可以证明，最终 部分的系数一定抵消。故只提取 即可得到答案。

---

卡常技巧：

• 计算 时，可以计算 ，即可通过加减法得到所需的 。

  这需要计算 的 DFT，再进行三次 IDFT，共 次。

• 之间的关系类似于共轭，于是可以证明，两者的 次幂中， 的系数仍为相反数。

  因此只需计算一次快速幂。

• 计算快速幂时，将求平方精细实现。复用 DFT 结果。