多项式除法 | 取模

Description

给定多项式 ，求 除 的商 和余数 。

Method

发现若能消除 的影响则可直接

考虑构造变换

观察可知其实质为反转 的系数。

设 。

将 中的 替换成 并将其两边都乘上 ，得到：

注意到上式中 的系数为 ，则将其放到模 意义下即可消除 带来的影响。

又因 的次数为 ，故 不会受到影响。

则：

使用多项式求逆即可求出 ，将其反代即可得到 。

时间复杂度 。