拉格朗日插值法 入门

一 简介

一种[在模意义下已知多项式任意点值表示,求一个新的点值]的方法

时间复杂度O(n^2),在已知点值连续时可以做到O(n)

长这样:

二 证明

显然有f(k)≡f(xi)(mod k-xi)

解中国剩余定理即可

三 典中点

(以下代码实现省略部分经典函数和取模)

P4781 【模板】拉格朗日插值 

O(N^2)实现任意点值实例

这个是板子(按理来讲这个板子是不严谨的)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5,mod=998244353;

int n,k,a[N],b[N],ans;

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i)
      a[i]=read(),b[i]=read(); 
    for(int i=1;i<=n;++i){
        int up=1,dowm=1;
        for(int j=1;j<=n;++j)
          if(i!=j)
            up=up*(k-a[j]),
            dowm=dowm*(a[i]-a[j]);
        ans=ans+b[i]*up%mod*ny(dowm);
    }
    printf("%lld",ans);
    return 0;
}
CF622F The Sum of the k-th Powers

O(N)实现连续点值实例

可以证明他是一个k+1多项式

构造f(x)=1^k+2^k……+x^k=那个k+1次的求和多项式

取(k+1)+1个点值(取1~k+2显然很简单),然后把n插进去就可以了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//f(n)=∑f[i]*π (n-j)/(i-j)
//fz=π(n-i)
 //f(n)=∑f[i]*fz/(n-i)/π(i-j)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k,f[N],ans;
int fac[N],fz=1;

signed main(){

    n=read(),k=read()+1;

    for(int i=1;i<=k+1;++i)
      f[i]=ksm(i,k-1)+f[i-1];

    fac[0]=1;
    for(int i=1;i<=k+1;++i)
      fac[i]=fac[i-1]*i;
    for(int i=1;i<=k+1;++i)
      fz=fz*(n-i);

    if(fz){
        for(int i=1;i<=k+1;++i)
          ans = ans + ((k+1-i)&1?-1:1) * f[i] * fz * ny(n-i) * ny(fac[k+1-i]*fac[i-1]) ;
        printf("%lld",ans);
    }
    else{
        for(int i=1;i<=k+1;++i)
          if((n-i)%mod==0){
            ans=f[i];
            for(int j=1;j<=k+1;++j)
              if(i!=j)
                ans = ans * (n-j) * ny(i-j,mod-2);
            printf("%lld",ans);
          }
    }
    return 0;
}