标签：拉格朗 前缀 次数 插值 多项式 差分 浅浅

关于拉格朗日插值 我懒得打\(LaTeX\) 所以大概只讲一下思路

拉格朗日插值

这个东西的思想就是 当我们要求的东西其实可以被看做一个多项式的点值时 我们不需要求出每一个具体的值 只需要求出其次数+1个值就可以确定这个多项式

那这个东西是什么原理呢 看oi-wiki

其实证明就是一个广义一点的中国剩余定理 看懂求的那个逆元为什么对就挺平凡的

正常的拉格朗日差值是\(n^2\)出值 但是当点的横坐标之差不变时可以通过预处理达到\(O(n)\)的复杂度

而且更离谱重要的是插值这个过程一般都是我们自己来 所以插值一般\(O(n)\)就随便做了

首先什么东西是一个多项式

看起来像就是

洛谷标签写着是就是

比较像的就是一个数学式子 \(\sum\)后面跟个什么次方之类这玩意一看就很数学的

比较离谱的比如一个dp之类的递推式跟前缀和相关云云 一般递推关系比较不简单可以直接不考虑了 如果跟前缀相关可以直接把点值前缀然后直接对前缀插值

多项式次数怎么求

首先你的点值多了是不影响的 所以建议拿大样例二分次数反正它满足单调性嘛

一般来说对一个已知的多项式多点值求和次数要加1加2的 废话

更常被引用的是自然幂级数推论 但我估计没几个人具体知道这是啥 我百度都搜不出来

来一个典型例子：

\[\sum_{i=1}^{\infty} i^k \]

这个东西是一个\(k+1\)次多项式 需要\(k+2\)个值

为啥呢？

差分 不断差分到差分出来结果为\(0\)就求出了次数

因为每一次差分都会让次数\(-1\)

例：\({(x+1)}^3-x^2=3x^2+3x+1\)

简直毫无关系是吧

P4463 calc 普通版是拉格朗日优化dp 挺好的题

标签：拉格朗,前缀,次数,插值,多项式,差分,浅浅
From： https://www.cnblogs.com/Sakura-Lu/p/16817838.html