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


描述

给定多项式 ,求模 意义下的

解法

普通方法


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

定义,其必须满足:

求导再积分,可得:

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


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

否则 的常数项不收敛。

求导,可得:

比较两边系数可得:

,则:

使用分治 FFT 即可解决。

时间复杂度

Newton's Method

使用

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

代码

例题

  1. 计算

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

时,有:

时,设 的最低次项为 ,则:

时间复杂度

贡献者:@CCXXXI@mgt@H-J-Granger@Ir1d@Marcythm@xzz@ouuan@雷蒻@97littleleaf11@abc1763613206@TrisolarisHD

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组