luogu4781

由小学知识可知 n 个点 (x_i,y_i) 可以唯一地确定一个多项式 y = f(x)。

现在，给定这 n 个点，请你确定这个多项式，并求出f(k)mod998244353 的值。

第一行两个整数 n,k。

接下来 n 行，第 i 行两个整数 x_i,y_i​。

一行一个整数，表示 f(k)mod998244353 的值。

样例一中的多项式为 f(x)=x^2+2x+1，f(100) = 10201。

样例二中的多项式为 f(x)=x，f(100) = 100。

1≤n≤2×103，1≤xi​,yi​,k<998244353，x_i两两不同。

__________________________________________________

拉格朗日插值

给定n+1个点（x_0,y_0）,(x_1,y_1),...,(x_n,y_n)

确定a_1*x^n+a_2*x^(n-1)+a_3*x^(n-2)+...+a_(n+1)*x^0

实际就是把n个点代入，解出n+1个系数。

再给你一个x求出对应的y值。

但是这个方法太慢，于是可以用拉格朗日插值法构造出这个函数，并解出y的值。

方法如下：

根据（x_0,y_0）我们可以构建一个函数，当x=x_0时，y=y_0；而代入x=x_1,x_2,...,x_n时y=0

y=y_0*((x-x_1)(x-x_2)(x-x_3)...(x-x_n))/((x_0-x_1)(x_0-x_2)(x_0-x_3)...(x_0-x_n))

同样的方法，我们可以其它点构造出对应的函数。

y=y_1*((x-x_0)(x-x_2)(x-x_3)...(x-x_n))/((x_1-x_0)(x_1-x_2)(x_1-x_3)...(x_1-x_n))

y=y_2*((x-x_0)(x-x_1)(x-x_3)...(x-x_n))/((x_2-x_0)(x_2-x_1)(x_2-x_3)...(x_2-x_n))

...

y=y_n*((x-x_0)(x-x_1)(x-x_2)...(x-x_n-1))/((x_n-x_0)(x_n-x_1)(x_n-x_2)...(x_n-x_n-1))

然后把它们加起来就是我们要的函数

y=sum_{i=0}^n y_i * prod _{i=0,i eq j}^n (x-x_j)/(x_i-x_j)

这样就可以用O(N^2)完成

__________________________________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2010;
 4 const int mod=998244353;
 5 int n;
 6 int x[maxn],y[maxn],xx;
 7 int qpow(int x,int p)
 8 {
 9     if(p==0)return 1;
10     int tp=qpow(x,p/2);
11     tp=1ll*tp*tp%mod;
12     if(p%2)tp=1ll*tp*x%mod;
13     return tp;
14 }
15 int lagrange(int n,int *x,int *y,int xi)
16 {
17     int ans=0;
18     for(int i=1;i<=n;++i)
19     {
20         int fz=1,fm=1;
21         for(int j=1;j<=n;++j)
22         {
23             if(i==j)continue;
24             fz=1ll*fz*(xi-x[j])%mod;
25             fm=1ll*fm*(x[i]-x[j])%mod;
26         }
27         ans=(1ll*ans+1ll*y[i]*fz%mod*qpow(fm,mod-2)%mod)%mod;
28     }
29     return (ans+mod)%mod;
30 }
31 
32 int main()
33 {
34     scanf("%d%d",&n,&xx);
35     for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
36     cout<<lagrange(n,x,y,xx)<<endl;
37     return 0;
38 }

View Code