多项式平移|连续点值平移
多项式平移
多项式平移是简单情况的多项式复合变换,给出
分治法
令
那么
其中
Taylor 公式法
对
那么
观察到对于
令
那么
二项式定理法
考虑二项式定理
得到的结果与上述方法相同。
连续点值平移
给出度数小于等于
Lagrange 插值公式法
考虑 Lagrange 插值公式
上式虽然是卷积形式但不能保证分母上
那么对于
实现中取
对问题稍加修改,假设对于某个
Lagrange 插值公式也给出了通过维护一些前后缀积的线性计算单个点值的方法。
应用
同一行第一类无符号 Stirling 数
在模素数
考虑
其中
通过多项式平移可在
模素数意义下阶乘
求
令
其中
多项式多点求值
连续点值平移
令
所以只需
由
额外增加的一个点值使用线性时间的算法即可。那么在开始时维护
而我们只需要约
模素数意义下二项式系数前缀和
求
考虑使用矩阵描述
类似的可以将二项式系数前缀和的递推描述为
注意矩阵乘法的顺序,那么
令
的点值
且矩阵右下角元素恰为我们在阶乘算法中所维护的,那么
可在
模素数意义下调和数
求
记
那么
在这里
参考文献
- Alin Bostan, Pierrick Gaudry, and Eric Schost. Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator.
- Min_25 的博客
- ZZQ 的博客 - 阶乘模大质数
本页面最近更新:2/3/2023, 12:00:00 AM,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用