2019年7月2日，整理总结
2020年4月16日，更新O(n)的情形，注意值连续时，拉格朗日插值可以优化到O(n)(n是多项式次数)
思路来源https://www.cnblogs.com/zwfymqz/p/10063039.html(自为风月马前卒大佬)
https://www.cnblogs.com/cjyyb/p/9392388.html（O(n*n)板子）
https://www.cnblogs.com/cjyyb/p/9392911.html（洛谷P4781题解）
https://blog.csdn.net/BeNoble_/article/details/79512449（化简证明1）
https://blog.csdn.net/weixin_38686780/article/details/81155608（化简证明2）
https://blog.csdn.net/GodJing007/article/details/91348487（南昌邀请赛拉格朗日插值）
https://blog.csdn.net/GodJing007/article/details/90957805（重心拉格朗日插值）
知识整理（截图自化简证明1+化简证明2）①如果n次多项式已知的点是连续的，求一个值的复杂度是的，
即对于次多项式，若知道的值，对于一个给定的，可以地求出的值
公式：
证明：
分母是阶乘的逆元，可在O(d)时间复杂度下预处理，
分子前半段是前缀积，后半段是后缀积，可在n给定的情形下O(d)处理
对于每个n，O(d)的求和即可，这里d=k+1
例题
2019ICPC南昌邀请赛B-Polynomial
已知前n项的值，对于每个询问O(n)处理
把所有ll改成int会快很多，所以mod数小于int32时，数组都开int
先插出f(n+1)的值，然后根据n+2个值，预处理前缀和函数sum(0)到sum(n+1)
对于询问l和r，插出sum(r)和sum(l-1)单点作差即可
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=9999991;const int N=1e3+10;int t,n,m,l,r;int a[N],sum[N],pre[N],suf[N];int fac[N],finv[N];int modpow(int x,int n,int p){int res=1;for(;n;x=1ll*x*x%p,n>>=1)if(n&1)res=1ll*res*x%p;return res;} int cal(int *f,int mx,ll n)//已知f[0]到f[mx] 求f[n] 注意n的范围{ if(n<=mx)return f[n]; int ans=0;pre[0]=suf[mx]=1;for(int i=1;i<=mx;++i)pre[i]=1ll*(n-i+1)%mod*pre[i-1]%mod;//注意到(n-i+1)*pre[i-1]在有些题可能爆ll 先%for(int i=mx;i>=1;--i)suf[i-1]=1ll*(n-i)%mod*suf[i]%mod;for(int i=0;i<=mx;++i){int sg=(mx-i)&1?-1:1;ans=ans+1ll*sg*pre[i]%mod*suf[i]%mod*finv[i]%mod*finv[mx-i]%mod*f[i]%mod;if(ans>=mod)ans-=mod;if(ans<0)ans+=mod;} return ans;}void init(){fac[0]=1;for(int i=1;i<N;++i)fac[i]=1ll*fac[i-1]*i%mod;finv[N-1]=modpow(fac[N-1],mod-2,mod);for(int i=N-1;i>=1;--i)finv[i-1]=1ll*finv[i]*i%mod;}int main(){ init(); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) scanf("%d",&a[i]); a[n+1]=cal(a,n,n+1);//插出f(n+1) sum[0]=a[0];//非常关键 别忘了 for(int i=1;i<=n+1;i++) sum[i]=(sum[i-1]+a[i])%mod; while(m--){ scanf("%d%d",&l,&r); int cnt=cal(sum,n+1,r)-cal(sum,n+1,l-1); if(cnt<0)cnt+=mod; printf("%dn",cnt); } } return 0;}②如果n次多项式已知的点不是连续的（是任意的），求一个值的复杂度是的，
公式：
证明：
举个例子理解一下，假设给出的三个点为，直接把展开，
观察不难得到，如果我们把带入的话，除第项外的每一项的分子中都会有为0，
这样其他的所有项就都被消去了，必有成立
例题洛谷P4781
给出非前n项的n个(xi,yi)，对于每个位置处理
代码来自：https://www.cnblogs.com/cjyyb/p/9392911.html
#include<cstdio>#define ll long long#define MOD 998244353#define MAX 2020inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int n,K,x[MAX],y[MAX],ans;int fpow(int a,int b){ int s=1; while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;} return s;}int main(){ n=read()-1;K=read(); for(int i=0;i<=n;++i)x[i]=read(),y[i]=read(); for(int i=0;i<=n;++i) { int tmp=1; for(int j=0;j<=n;++j) if(i!=j)tmp=1ll*tmp*(K-x[j])%MOD*fpow(x[i]-x[j],MOD-2)%MOD; ans=(ans+1ll*y[i]*tmp)%MOD; } ans=(ans+MOD)%MOD;printf("%dn",ans); return 0;}