Luogu7439 「KrOI2021」Feux Follets 弱化版

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

其中 是长度为 的错排。

，时限 。

---

此时 较大，故不一定需要使用牛顿级数。下文默认 同阶。

首先用多点求值得到 ，然后求出 的系数，点乘即可得到答案。

因此，在加强后的问题中，多项式 的存在仅仅是提供了一个贡献系数序列……

考虑拉格朗日反演来快速求出 。

首先用多项式复合描述问题。设 ，则 。

此处 并不存在复合逆，但有 ，于是设 ，此时 ，故 显然有复合逆，设为 。

并改写 ，于是仍有 。

套用扩展拉格朗日反演，可得：

算得 。记 。

于是，在求出 之后可以 得到 。

注意到 有一个较为简单的封闭形式，考虑利用牛顿迭代求复合逆 。

于是可以牛顿迭代，倍增式为 ：

注意分母 常数项为 ，故做除法时需要分子分母先除去一个 。这会导致次数并非严格倍增。

复杂度同为 。

多点求值的复杂度为 ，注意常数优化。