多项式多点求值求值函数c++实现

来源：蜘蛛抓取(WebSpider) 时间：2018-07-18 10:31 标签： 多项式求值

首先根据拉格朗日插值公式我们可以暴力\(O(n^2)\)插出这个多项式多点求值然而这显然是\(gg\)的

那么看看怎么优化，先来看一看拉格朗日插值的公式

这分子分母全為\(0\)我怎么求啊……

根据我也不知道是啥的洛必达法则如果

先分治\(NTT\)算出\(g\)，然后多点求值把每个点处的值算出来就好了

闲来无事写了一个多项式多点求值之间的加减乘除 

// 多项式多点求值.cpp : 定义控制台应用程序的入口点。

我要回帖

更多关于 多项式求值 的文章

 

随机推荐