摘要:点值表达还原多项式

拉格朗日插值法

给出n个点$P_i(x_i,y_i)$,将过这n个点的n-1项多项式记为$f(x)$,求$f(k)$的值.

将这n个点在x轴上的投影$(x_i,0)$记为$H_i$,考虑构造一个多项式$g_i(x)$过投影中n-1个点,并在$x_i$处取到$y_i$.

很好构造出:

所以说$f(x)=\sum_{i=1}^n g_i(x)$,得到:

这样多项式就还原出来了,复杂度$O(n^2)$,题目只求一个$f(k)$,带入k即可.

板子

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl maxn=2010,mod=998244353;
lxl n,k,s1,s2,ans;
lxl x[maxn],y[maxn];
inline lxl FastPow(lxl a,lxl b)
{
lxl sum=1;
for(;b;b>>=1,a=a*a%mod)(b&1)&&(sum=sum*a%mod);
return sum;
}
inline lxl inv(lxl a)
{
return FastPow(a,mod-2);
}
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
int main(void)
{
n=read(),k=read();
for(R int i(1);i<=n;x[i]=read(),y[i++]=read());
for(R int i(1);i<=n;++i)
{
s1=y[i]%mod,s2=1;
for(R int j(1);j<=n;++j)
if(i!=j)s1=s1*((k-x[j]+mod)%mod)%mod,s2=s2*((x[i]-x[j]+mod)%mod)%mod;
ans=(ans+s1*inv(s2)%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}