Luogu7440 「KrOI2021」Feux Follets

题意：给定两个整数 和一个 次多项式，对 分别求

其中 是长度为 的错排。

，时限 。

---

• 前置芝士：转置原理。

继承 Luogu7439，仍然首先搞一手多点求值，则有

记 。

以线性变换的角度来看，将 视为输出向量， 视为输入向量，则贡献矩阵 。

考虑该变换的转置，即 ，写出和式 ：

考虑 的生成函数 ，则可写作

将 按 切分，设 。

求导可得

由此不难得到递推式

边界为 ，为了方便，令 ，这样就能一直套用递推式。

将转移写成矩阵 ，满足

则有 ，于是

则答案可以改写为 ： 最终取出矩阵右下角即为答案。

这可以利用分治 FFT 计算。设 边界为 。

有转移：

注意矩阵乘法不满足交换律，故转移中的乘法顺序必须严格考虑。

将该算法转置即可。

矩阵乘法的转置相当于用转置乘法计算转置后矩阵的乘法。

将输入塞在原来答案的位置，输出就会出现在原来输入的位置。

复杂度为 ，常数较大。