多项式求逆

描述

给定多项式 ，求 。

解法

倍增法

首先，易知

假设现在已经求出了 在模 意义下的逆元 。 有：

两边平方可得：

两边同乘 并移项可得：

递归计算即可。

时间复杂度

Newton's Method

参见

Newton's Method.

Graeffe 法

欲求 考虑

只需求出 即可还原出 因为 是偶函数，时间复杂度同上。

代码

例题

1. 有标号简单无向连通图计数：「POJ 1737」Connected Graph