多项式对数函数|指数函数

描述

给定多项式 ，求模 意义下的 与 。

解法

普通方法

---

首先，对于多项式 ，若 存在，则由其

定义，其必须满足：

对 求导再积分，可得：

多项式的求导，积分时间复杂度为 ，求逆时间复杂度为 ，故多项式求 时间复杂度 。

---

首先，对于多项式 ，若 存在，则其必须满足：

否则 的常数项不收敛。

对 求导，可得：

比较两边系数可得：

又 ，则：

使用分治 FFT 即可解决。

时间复杂度 。

Newton's Method

使用

Newton's Method 即可在 的时间复杂度内解决多项式 。

代码

例题

1. 计算

普通做法为多项式快速幂，时间复杂度 。

当 时，有：

当 时，设 的最低次项为 ，则：

时间复杂度 。