单位根(unit root):次单位根记做

单位根反演

如同大多数反演一样,单位根反演(unit root inversion)也是基于一个恒等式:

证明

,则上式显然等于

否则,根据等比数列求和公式可以得到

证毕。

数论中的单位根

上午中的单位根需要满足什么性质吗?次单位根需要满足,),。并不需要其他的条件。因此如果你担心浮点数运算的速度和精度问题,可以考虑在模意义下找到次单位根——也就是阶为的数。

生成函数与单位根反演

考虑一个 OGF。我们想求所有指数是的倍数的项的系数和,也就是。单位根反演一波得到

那么只要我们能快速计算函数的点值,就可以快速计算上述的系数和。

LJJ 学二项式定理

给定,求

构造 OGF。那么我们只需要知道下标的四种余数的系数和,就可以求出答案了。

对于,即,我们可以直接反演。如果余数非零,那么我们可以给来右移位,然后也可以反演。因此接下来的问题是:

  • 单位根是多少。
  • 的点值如何快速计算。

由于模数特殊,容易发现

根据二项式定义,容易得到

因此时间复杂度

代码

PYXFIB

给定,求

其中是斐波那契数列,

是质数。

容易发现我们要求是

到这里有两种算法。

算法一

单位根反演的结论在矩阵意义上也是成立的。设表示对应的矩阵。因此我们要求是

那么构造 OGF。由于是质数且,因此我们找到的一个原根,就可以得到。这样就可以单位根反演了。

时间复杂度

算法二

其实斐波那契数列本身就可以表示成等比数列的和的形式。使用特征根或者生成函数法可以得到

那么我们求两次即可。单位根还是按照算法一的方式求出。使用类似的方法构造生成函数。

然后还是对扩域再计算。

时间复杂度